조이스틱(프로그래머스-탐욕법(Greedy))

문제

코드

class Solution {
    static int answer=Integer.MAX_VALUE;
    public int solution(String name) {
        dfs(0,0,0,new boolean[name.length()],name);
        return answer;
    }
    public static void dfs(int index,int move,int count,boolean[] visit,String name){
        boolean[] visited=visit.clone();       
        visited[index]=true;
            if(name.charAt(index)!='A'){
                if(name.charAt(index)-'A'<14)
                    count+=name.charAt(index)-'A';
                else 
                    count+=26-(name.charAt(index)-'A');
                count+=move;
                move=0;
            }
        
        boolean hasNext=false;
        int next;
        for(int i=1;i<name.length();i++){
            if(index+i>=name.length()) next=index+i-name.length();
            else next=index+i;
            if(name.charAt(next)!='A'&&!visited[next]){
                dfs(next,i,count,visited,name);
                hasNext=true;
                break;
            }
        }
        
        for(int i=1;i<name.length();i++){
            if(index-i<0) next=name.length()+index-i;
            else next=index-i;
            if(name.charAt(next)!='A'&&!visited[next]){
                dfs(next,i,count,visited,name);
                hasNext=true;
                break;
            }
        }

        if(!hasNext) answer=Math.min(answer,count);
        

    }
}

풀이

이 문제를 해결하기 위해서는 두가지를 최소화 해야 한다.
1. 조이스틱 위 아래(알파벳을 바꿀 때) 움직임 최소화
2. 조이스틱 좌 우(커서 교체) 움직임 최소화
이를 염두해 두고 다음과 같은 과정을 거친다.
(1) dfs 알고리즘을 사용하여 문제를 해결한다. 이 문제의 핵심은 조이스틱의 좌 우(커서 교체)를 최소화 하는 것이다. 커서의 움직임은 결국 좌,우의 두가지 경우의 수 이기 때문에 한 알파벳을 확인한 후, 왼쪽으로 커서를 이동하는 경우와 오른쪽으로 커서를 이동하는 경우로 나누어 dfs 알고리즘을 실행해 주면 된다.
(2) 다음 확인할 알파벳("A"가 아닌 알파벳)을 찾으면, 방문체크를 한 후 알파벳을 바꾸기 위해 움직여야 하는 조이스틱 횟수의 최소값을 수해야 한다.
-> 알파벳은 총 26개 이다. 즉, A에서 13번째 이상으로 떨어진 알파벳을 찾기 위해서는, 거꾸로 가는 것이 더 효율적이다.
(3) 위와 같은 방법으로, 조이스틱 위 아래 움직임을 count 해주고, 이동했던 커서 움직임 만큼도 count해준다.
(4) (3)이 끝났다면, 다음 확인할 알파벳을 찾는다. 이 때 (1)의 방법을 사용한다.
(5) 더이상 확인할 알파벳이 없다면, 계산한 count값을 통해 최솟값을 answer로 갱신하여 반환한다.

결과

문제 카테고리가 그리디 알고리즘으로 나와있어서, 처음에는 당연히 그리디한 방법을 생각했다. 대충 커서를 왼쪽으로 쭉 갈지, 오른쪽으로 쭉 갈 지만 정하면 되겠구나 생각했는데, 왼쪽으로 가다가 오른쪽으로 가는 것이 더 적은 총 횟수가 나올 수 있다는 것을 알고 dfs방법으로 바꿔 풀었다. 문제의 의도는 그리디 인것 같은데, 어떤 방법으로 풀어야 할지 생각이 나지 않는다.
제한사항에서 name의 길이가 짧기 때문에, dfs로 풀어버리는게 편하긴 하다.
지금 프로그래머스에서 카테고리 별로 고득점 Kit을 풀어보고 있는데, 미리 카테고리를 알고 풀다보니까 그쪽으로만 생각하게 된다.
카테고리를 신경쓰지 않고 해야겠다.
출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges