[Programmers/Level 2/Java] 조이스틱

Programmers(프로그래머스) 조이스틱

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

문제 설명

조이스틱으로 알파벳 이름을 완성하라.
처음에는 모두 A로만 이루어져 있으며, 상하로 알파벳을 선택하고, 좌우로 커서를 옮길 수 있다.
첫번째 위치에서 조이스틱을 왼쪽으로 조작하면 마지막 위치로 커서를 이동하고,
"A"에서 조이스틱을 위쪽으로 조작하면 "Z"로 입력된다.

예)
"JAZ"라는 이름을 만들기 위해, "AAA"에서 조이스틱을 다음과 같이 움직여야 한다.
- 첫번째 알파벳 "J"를 만들기 위해 조이스틱을 아래로 9번 조작  -->  "JAA"
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동  -->  "JAA"
- 세번째 알파벳 "Z"를 만들기 위해 조이스틱을 위로 1번 조작  -->  "JAZ"

풀이

프로그래머스 문제 분류에도 나와있듯이, 탐욕법(Greedy Argorithm)으로 풀 수 있는 문제이다.

주의해야할 점은,
1) 알파벳을 조작할 때 위로 조작하는 것이 횟수가 적을지, 아래로 조작하는 것이 횟수가 적을지 판단해야 하고,
2) 알파벳을 조작한 후에는 어디로 이동해야 커서 이동을 최소화하면서 알파벳을 완성시킬 수 있을지 고민해야 한다.

2)번을 더 살펴보자면, "JBACAAAAAAZ" 같은 알파벳 이름이 주어졌을 때에 단순히 왼쪽에서 오른쪽으로 이동하면서 완성하는 것보다는, "J", "B", "C"까지 왼쪽에서 오른쪽으로 이동하면서 완성한 후, 왼쪽으로 이동해 "Z"를 찾아 완성하는 것이 더 조작 횟수가 적다는 것을 유의해야 한다는 것이다.

class Solution {
    public int solution(String name) {
        int answer = 0;
        boolean[] arrayCompleted = new boolean[name.length()];   // 완성된 알파벳인지 체크
        int cntCompleted = 0;   // 완성된 알파벳 수
        int index = 0;  // 커서 위치
        
        while(true)
        {
            // 현재 위치(index)의 알파벳 완성
            int move = 0;
            if(name.charAt(index) - 'A' > 13)
                move = 'Z' - name.charAt(index) + 1;
            else
                move = name.charAt(index) - 'A';
            
            // 알파벳 완성 여부 체크
            arrayCompleted[index] = true;
            cntCompleted++;

            // 오른쪽으로 이동하면서 바꿀 알파벳 탐색
            int right;
            for(right = 1; right < name.length(); right++)
            {
                int nextIndex = (index + right) % name.length();
                // 완성된 알파벳이라고 체크가 되어 있지 않을 때,
                if(!arrayCompleted[nextIndex])
                { 
                    // 목표 알파벳이 'A'라면 조이스틱 조작 없이 완성 체크만 함
                    if(name.charAt(nextIndex)== 'A')
                    {
                        arrayCompleted[nextIndex] = true;
                        cntCompleted++;
                    }
                    // 그렇지 않은 경우 조작해야할 알파벳 찾은 것임, 탐색 종료
                    else
                        break;
                }
            }
            
            // 왼쪽으로 이동하면서 바꿀 알파벳 탐색
            int left;
             for(left = 1; left < name.length(); left++)
            {
                int nextIndex = (name.length() + index - left) % name.length();
                
                if(!arrayCompleted[nextIndex])
                {
                    if(name.charAt(nextIndex) == 'A')
                    {
                        arrayCompleted[nextIndex] = true;
                        cntCompleted++;
                    }
                    else
                        break;
                }
            }
            
            // 현재 알파벳을 완성할 때 조이스틱 조작한 횟수 누적
            answer += move;
            
            // 모두 완성 했다면 종료
            if(cntCompleted >= name.length())
                break;
            
            // 바꿔야 할 알파벳들 중에서 왼쪽이 가까운 지, 오른쪽이 가까운 지 비교
            if(right <= left)
            {
                // 바꿔야 할 알파벳으로 이동, 이동한 만큼 조이스틱 조작 횟수 누적
                index = (index + right) % name.length();
                answer += right;
            }
            else
            {
                index = (name.length() + index - left) % name.length();
                answer += left; 
            }
        }
        return answer;
    }
}