C# 조이스틱 - 그리디 DFS / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/42860

 

 

1차 시도

public int solution(string name) 
{
    int answer = int.MaxValue;
    bool[] visited = name.Select(s => s == 'A').ToArray(); // A 는 방문안해도 됨
    Greedy(name, visited, 0, 0, ref answer);

    return answer;
}

private void Greedy(string name, bool[] visited, int cur, int count, ref int answer)
{
    if(!visited[cur]) // A 면 이미 visited이니 무시한다.
    {
        // n 위치의 알파벳을 위나 아래로 옮기는 것 중 빠른 쪽으로 맞춘다.
        int up = name[cur] - 'A'; // ▲ - 다음 알파벳
        int down = 'Z' - 'A' - up + 1; // ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
        count += Math.Min(up, down);

        visited[cur] = true;
    }

    if(visited.Count(c => !c) == 0)
    {
        if(count < answer)
            answer = count;

        return;
    }

    // ◀ - 커서를 왼쪽으로 이동
    int left = cur;
    int leftCount = 0;
    while (visited[left])
    {
        ++leftCount;
        left = left > 0 ? left - 1 : (left + name.Length - 1) % name.Length;
    }

    // ▶ - 커서를 오른쪽으로 이동
    int right = cur;
    int rightCount = 0;
    while (visited[right])
    {
        ++rightCount;
        right = right < name.Length - 1 ? right + 1 : (right + 1) % name.Length;
    }

    if(leftCount < rightCount)
        Greedy(name, visited, left, count + leftCount, ref answer);
    else
        Greedy(name, visited, right, count + rightCount, ref answer);
}

프로그래머스는 분류가 표시되는 문제가 몇개 있는데,

어떤 방식으로 문제를 접근해야 하는지를 알려주기 때문에 큰 힌트로 작용하는 경우가 많다.

이 문제는 그리디로 분류되어있어 그리디 방식으로 풀기로 했다.

 

양쪽 방향이 가능하다는 점에서 최근에 풀었던 문제와 비슷한 문제로 보인다. 

2023.03.29 - [코딩 테스트] - C# 마법의 엘리베이터 - DFS / 프로그래머스 [Lv.2]

 

재귀 탈출

보통은 재귀탈출을 맨 앞에 두지만, 순서대로 순회하지 않기 때문에 visited가 모두 true인 상황에서 탈출해야한다.

이 경우에도 visited를 매번 Count하지 말고 visitedCount 라는 int 변수를 별도로 만들어서 관리해도 좋을 듯 하다.

 

커서의 왼쪽, 오른쪽 이동

Array.IndexOf 와 Array.LastIndexOf 를 사용해서 직접 인덱스를 구해서 풀어도 될 것 같은데 한개 씩 더해가는 방식이 직관적이라서 우선은 while문으로 하나씩 인덱스를 더해가면서 체크하기로 했다.

 

3ms 정도로 성능은 문제없는 듯 하고, 정확성 74로 예외 케이스를 일부 처리 못했다.

 

 

 나의 풀이

public int solution(string name) 
{
    int answer = int.MaxValue;
    bool[] visited = name.Select(s => s == 'A').ToArray(); // A 는 방문안해도 됨
    DFS(name, visited, 0, 0, ref answer);

    return answer;
}

private void DFS(string name, bool[] visited, int cur, int count, ref int answer)
{
    if(!visited[cur]) // A 면 이미 visited이니 무시한다.
    {
        // n 위치의 알파벳을 위나 아래로 옮기는 것 중 빠른 쪽으로 맞춘다.
        int up = name[cur] - 'A'; // ▲ - 다음 알파벳
        int down = 'Z' - 'A' - up + 1; // ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
        count += Math.Min(up, down);

        visited[cur] = true;
    }

    if(visited.Count(c => !c) == 0)
    {
        if(count < answer)
            answer = count;

        return;
    }

    // ◀ - 커서를 왼쪽으로 이동
    int left = cur;
    int leftCount = 0;
    while (visited[left])
    {
        ++leftCount;
        left = left > 0 ? left - 1 : (left + name.Length - 1) % name.Length;
    }

    // ▶ - 커서를 오른쪽으로 이동
    int right = cur;
    int rightCount = 0;
    while (visited[right])
    {
        ++rightCount;
        right = right < name.Length - 1 ? right + 1 : (right + 1) % name.Length;
    }

    DFS(name, visited, left, count + leftCount, ref answer);
    visited[left] = false;

    DFS(name, visited, right, count + rightCount, ref answer);
    visited[right] = false;
}

1차 시도에서는 왼쪽으로 커서를 움직이는 경우와 오른쪽으로 커서를 움직이는 경우 중 더 작은 쪽 (Greedy)로 풀었는데,

이 경우 한쪽 방향으로 잠깐 갔다가 다시 반대쪽으로 가는 경우를 잘 처리 하지 못했던 듯 하다.

 

Greedy대신 DFS 로 좌우 방향으로 가는 경우를 둘 다 계산에 포함시켰더니 통과했다.

 

결국 다른 문자끼리 영향을 받지않고 단독으로 수행되는 위, 아래 버튼은 그리디가 맞고

앞서 선택된 위치에 영향을 받는 좌우 커서는 DFS로 풀어야하는 복합문제이다. 

성능도 거의 차이가 없는 수준이다.