[프로그래머스/Java] 조이스틱(Greedy 문제) 풀이

프로그래머스 코딩테스트 알고리즘 고득점 Kit 중 Greedy 알고리즘 파트에 해당하는 '조이스틱' 문제를 Java로 풀어보았다. 

https://school.programmers.co.kr/learn/courses/30/lessons/42860

프로그래머스

 

 

 이 문제는 Greedy 파트에 있는 문제이지만, greedy로 풀기는 너무 복잡한 문제였다. 각 커서에서 현재의 최단거리를 알 수 있다고 하나, 실상 그 방법이 더 효율이 떨어지고 확인해야 하는 부분이 너무 많다고 느껴졌다. 

 그래서 나는 아래 코드처럼 리스트를 활용해서 풀었다. 우선 알파벳 단위로 움직여 줘야 하는 부분, 즉 커서를 위아래로 움직여야 하는 부분부터 계산을 해주었다. 이 부분은 비교적 쉽다. 우리가 탐색 중인 알파벳이 'A'와 'Z' 중 어느 쪽과 더 가까운지 파악하여 거기서부터 움직이는 것으로 계산해 주면 되기 때문이다. 다만 'Z'부터 시작하는 경우, 실상 'A'에서 'Z'로 먼저 1만큼 이동해야 하기 때문에 이를 고려해줘야 한다.

 다음으로는 커서를 양옆으로 이동하는 것을 계산해줘야 한다. 나는 이를 세가지 경우로 나눠놓고 풀었다.

1. index 0부터 시작하여 차례로 오른쪽으로만 움직이는 경우
2. 마지막 index 부터 시작하여 차례로 왼쪽으로만 움직이는 경우 (index 0 -> 마지막 index -> 왼쪽으로만 이동)
3. 특정 인덱스까지는 오른쪽/왼쪽으로만 이동하고 다시 시작점으로 돌아가서 다시 왼쪽/오른쪽으로만 이동하는 경우

 

1번의 경우는 쉽다. 문제에서 예시로 주어진 "JEROEN"이 그런 경우이다. 시작점인 인덱스 0에서 끝 인덱스까지 차례로 움직이면 된다. 2번의 경우도 비교적 쉽다. "AABCDE"가 그런 경우일 것이다. 시작점인 인덱스 0에서 커서를 왼쪽으로 움직이면 끝인덱스로 이동한다. 그리고 A가 반복해서 나오기 전까지 커서를 계속 왼쪽으로만 움직이면서 알파벳을 바꿔주면 된다. 문제가 되는 부분은 마지막이다. "BACVAAAAR", "FDAAAAEWCO"와 같은 경우이다. "BACVAAAAR"의 경우 커서를 왼쪽으로 움직여서 먼저 R을 바꿔준 후, 다시 시작점인 B로 돌아와서 V까지 차례로 바꿔줘야 한다. "FDAAAAEWCO"의 경우 D까지 먼저 바꿔주고 다시 왼쪽으로 움직여서 E까지 차례로 바꿔주어야 한다. 

 이러한 모든 경우들을 처리해주기 위해서 선택한 방식이, list를 사용하는 것이다. 알파벳을 움직이는 것, 즉 커서를 위아래로 움직이는 것을 처리해 주면서, 탐색 중인 알파벳이 A가 아닌 경우만 list에 index를 저장한다. A가 아닌 알파벳만 저장하는 이유는 앞서 예시들을 봐서 알 수 있다시피, 다른 알파벳에 접근하기 위해 꼭 지나쳐야 하는 경우가 아니라면 A에는 굳이 접근할 필요가 없기 때문이다. 이후 mov 변수를 만들어서 왼쪽으로만 움직이는 경우를 파악해 준다. list에 첫 번째로 저장되어 있는 값은 가장 처음 나온 A가 아닌 문자의 위치일 것이다. 그러므로 그 앞 문자들은 모두 A일 것이고, 굳이 고려해 줄 필요가 없기 때문에 (끝인덱스)~(list에 첫 번째로 저장된 인덱스)의 범위만 고려해 주면 된다. 여기서 끝 인덱스에 해당하는 len-1에 list.get(0)을 빼주는 게 아니라 len에다가 빼주는 이유는 앞서 언급했듯, 시작인덱스인 0에서 왼쪽으로 한 번 이동해 줘야 끝 인덱스로 갈 수 있기 때문이다. 두 번째로는 오른쪽으로만 가는 경우를 파악한다. 이 역시 list에 마지막으로 저장된 값은 가장 마지막으로 나온 A가 아닌 문자의 위치일 것이고, 그 뒤에 나오는 문자들은 모두 A일 것이기 때문에 굳이 고려해 줄 필요가 없다. 

 마지막으로 양옆으로 움직이는 경우를 처리해줘야 한다. 이 경우 현재 인덱스와 바로 전의 인덱스 사이의 값들은 모두 A이기 때문에 (0 ~ 바로 전 인덱스) + (현재 인덱스 ~ 끝인덱스) 이렇게 고려해준다. (0~ 바로 전 인덱스)까지를 오른쪽으로 움직이고, (현재 인덱스 ~ 끝인덱스)까지를 왼쪽으로 움직이게 될 것이다. 그리고 이들 중 더 짧은 쪽을 먼저 가준다. 이유는 먼저 가준 쪽은 다시 원점으로 돌아가기 위해서 왕복을 해야 하기 때문이다. 이렇게 파악한 움직임의 횟수 중 앞서 계산한 1, 2번보다 짧은 경우가 있다면 적용해 주면 된다. 

import java.util.*;

class Solution {
    final static int alphabet = 'Z' - 'A' + 1;
    public int solution(String name) {
        int answer = 0;
        int len = name.length();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            int cur = name.charAt(i) - 'A';
            if (cur < alphabet/2) answer += cur;
            else answer += alphabet - cur;
            if (cur != 0) list.add(i);
        }
        if (list.isEmpty()) return 0;
        
        int mov = len - list.get(0); //1.왼쪽으로만
        if (list.get(list.size()-1) < mov) mov = list.get(list.size()-1); //2.오른쪽으로만
        for (int i = 1; i < list.size(); i++) { //3.양옆으로
            int head = list.get(i-1);
            int tail = len - list.get(i);
            int n = (head < tail) ? (head*2 + tail) : (tail*2 + head);
            if (n < mov) mov = n;
        }
        
        return answer + mov;
    }
}