[프로그래머스] 조이스틱

programmers.co.kr/learn/courses/30/lessons/42860

코딩테스트 연습 - 조이스틱

 

문제는 위와 같으며, 탐욕법(Greedy)를 사용하여 문제를 해결하였습니다.

 

탐욕법(Greedy)

그리디 알고리즘(탐욕법, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법입니다. 전체적인 상황의 해결법을 제시하기 위해 각 단계별로 최적의 경로를 선택하고 그 경로 끝에 도출되는 값을 적절한 값이기를 바라며 문제를 해결하는 방법입니다.

 

하지만 매 순간순간 최적의 값을 선택한다고 해도 결과적으로 그 값이 최적이 아닐 수 있습니다. 쉬운 예로 마시멜로우를 지금 1개 받고, 1분 기다렸다가 2개를 받을 수 있다고 하면 결과적으로는 1분 대기 후 2개를 받는 것이 최적이겠지만 탐욕법에서는 지금 당장 마시멜로우를 얻는 경우가 최적이라고 생각할 것이기 때문입니다.

 

그래도 탐욕법을 사용하여 해결할 수 있는 문제에서는 최적의 해를 빠르게 찾아낼 수 있다는 장점이 있습니다.

 

---

다시 문제를 확인해보겠습니다. 이 문제는 원하는 문자열을 만들기 위해 조이스틱을 최소로 이동시키는 횟수를 구하는 문제이기 때문에 탐욕법을 사용하여 매 단계마다 다음으로 변경이 필요한 문자를 선택할 때 현 위치에서 가장 적게 조이스틱을 이동시키는 위치로 선택함으로써 문제를 해결할 수 있습니다.

 

문제의 조건 중 하나 짚고 넘어가야 할 것이 있습니다.

위 사진과 같이 조이스틱을 이동하는 방법이 나와있는데 커서를 오른쪽으로 이동하는 경우를 살펴보면 마지막 위치에서 오른쪽으로 이동하면 첫 번째 위치로 이동할 수 있다는 조건이 빠져있습니다. (암묵적으로 허용한 것 같습니다...ㅠ)

 

예를 들어 살펴보겠습니다. 문자열 "JAJAAAJ"가 주어졌을 때, 아래와 같은 과정을 통해 최소 31번 이동해야한다는 결과가 나옵니다.

 

정리해보면

1. 주어진 문자열을 char 배열로 전환합니다.

2. char 배열을 하나씩 확인하며 원하는 char가 나올 때까지 상하로 조이스틱을 이동시키는 횟수 중 최소값을 int 배열에 저장합니다. 

3. 현재 위치 문자(초기 위치는 0)부터 문자를 찾는데 걸린 이동 횟수를 총 이동 횟수에 추가한 뒤, 해당 문자는 더 이상 변경이 필요하지 않기 때문에 0으로 설정합니다.

4. 이후 현재 문자 위치부터 왼쪽으로 이동 시 가장 먼저 발견되는 변경이 필요한 문자까지 이동하는 횟수와 오른쪽으로 이동 시 가장 먼저 발견되는 변경이 필요한 문자까지 이동하는 횟수를 구합니다.

5-1. 왼쪽으로 이동하는 횟수와 오른쪽으로 이동하는 횟수 모두 0인 경우 더 이상 변경이 필요한 문자가 존재하지 않는 경우이므로 반복을 종료하고 지금까지 계산된 총 이동 횟수를 반환합니다.

5-2. 왼쪽으로 이동하는 횟수가 오른쪽으로 이동하는 횟수보다 작은 경우, 왼쪽으로 이동하는 것이 유리하다고 판단되어 다음 위치를 왼쪽으로 이동시킵니다. 이후 왼쪽으로 이동한 횟수를 총 이동 횟수에 더하고 다시 3번부터 위 과정을 반복합니다.

5-3. 오른쪽으로 이동하는 횟수가 더 작거나 같은 경우, 오른쪽으로 다음 위치를 이동시키고 오른쪽으로 이동한 횟수를 총 이동 횟수에 추가한 뒤 다시 3번부터 위 과정을 반복합니다.

 

자바 코드는 다음과 같습니다.

class Solution {
    public int solution(String name) {
        int answer = 0;
        char[] chars = name.toCharArray();
        int[] matchCount = new int[name.length()];

        // 각 문자를 가장 빠르게 찾는 횟수를 저장
        for (int i = 0; i < chars.length; i++) {
            matchCount[i] = findChar(chars[i]);
        }

        int start = 0;
        while (true) {
            answer += matchCount[start];  // 현재 위치 문자를 변경하는데 필요한 조이스틱 상하 이동 횟수 추가
            matchCount[start] = 0;  // 현재 위치 문자는 변경이 완료되었으므로 변경이 필요한 횟수 0으로 수정

            int leftMove = findIdx(matchCount, start, -1);  // 왼쪽으로 이동하면서 가장 가까운 변경이 필요한 문자까지의 이동 거리 구하기
            int rightMove = findIdx(matchCount, start, 1);  // 오른쪽으로 이동하면서 가장 가까운 변경이 필요한 문자까지의 이동 거리 구하기

            // 더 이상 변경이 필요한 문자가 존재하지 않는 경우 반복 종료
            if (leftMove == 0 && rightMove == 0) {
                break;
            }

            // 왼쪽으로 이동하는 것이 더 가까운 경우
            if (leftMove < rightMove) {
                start = start - leftMove >= 0 ? start - leftMove : matchCount.length - (leftMove - start);  // 조이스틱을 왼쪽으로 이동시키고
                answer += leftMove;  // 조이스틱을 왼쪽으로 이동시킨 횟수 추가
            } else {
                start = start + rightMove < matchCount.length ? start + rightMove : rightMove - (matchCount.length - start);  // 조이스틱을 오른쪽으로 이동시키고
                answer += rightMove;  // 조이스틱을 오른쪽으로 이동시킨 횟수 추가
            }
        }

        return answer;
    }
    
    // 'A' 부터 원하는 문자를 찾는데까지 조이스틱을 이동한 횟수 구하기
    // 위로 이동해서 찾은 경우와 아래로 이동해서 찾은 경우 중 더 작은 수를 반환
    private static int findChar(char current) {
        return Math.min(Math.abs('A' - current), Math.abs('Z' - current) + 1);
    }

    // 현재 위치부터 왼쪽 또는 오른쪽으로 이동하면서 변경이 필요한 문자까지 이동한 거리를 반환
    // 더 이상 변경이 필요한 문자가 없는 경우 0을 리턴
    private static int findIdx(int[] cnt, int cur, int direct) {
        int count = 0;
        int idx = cur;

        while (count < cnt.length) {
            count++;  // 이동 횟수 증가
            // direct에 맞게 왼쪽 또는 오른쪽으로 이동한 다음 위치 인덱스 구하기
            idx = idx + direct < 0 ? cnt.length - 1 : (idx + direct >= cnt.length ? 0 : idx + direct);

            // 다음 위치 문자가 변경이 필요한 문자인 경우
            if (cnt[idx] != 0) {
                return count;  // 이동 횟수 반환
            }
        }

        return 0;
    }
}