문제

문자열 JEROEN을 AAAAAA 상태에서 최소 몇번 이동으로 만들수있는지 물어보는 문제다.
링크

풀이

A->J 처럼 하나의 문자 변환은 상수시간에 해결 가능하다. 문자-'A'를 하면 A로부터 얼마나 떨어졌는지 확인이 가능하다. 만약 Z처럼 음에 방향으로 움직이려면 모듈러(%) 연산(26에서 빼줘도 가능)을 사용해주면 된다.

그러면 남은 연산은 왼쪽으로 진행할것인지 오른쪽으로 진행할것인지인데
처음에 무조건 한쪽 방향으로만 움직였다가 답이 나오지 않았다.

원점을 중심으로 지그재그처럼 움직여야하는 경우가 있기 때문이다.

그래서 각 움직임마다 양쪽 선택지를 주면 해결이 가능했다.

빅오는 첫번째 인덱스를 제외하고 2^(n-1)이 나온다. n이 20까지이므로 2^20=10^6 정도가 나오므로 시간안에 해결이 가능하다.

Code

package programmers;

class Solution_조이스틱 {
    private static int totalDiffCnt=0;
    private static final int MAX=(int)Math.pow(10,9);
    private static char[] carr,carr2;
    public int solution(String name) {
        // init
        carr=name.toCharArray();
        carr2=carr.clone();
        for(char c:carr){
            if(c!='A') totalDiffCnt++;
        }
        // move
        int start=0;
        int moveCnt=getAlphaDist(carr2[start]);
        int diffCnt=(moveCnt!=0)?1:0;
        carr2[start]='A';
        int ans=visit(start,diffCnt,moveCnt);
        carr2[start]=carr[start];
        return ans;
    }
    private int visit(int idx,int diffCnt,int moveCnt){
        if(diffCnt==totalDiffCnt){
            return moveCnt;
        }
        int leftVisit=MAX,rightVisit=MAX;
        // left
        for(int i=1;i<carr.length;i++){
            int leftIdx=(idx-i+carr.length)%carr.length;
            int leftVal=getAlphaDist(carr2[leftIdx]);
            if(leftVal!=0){
                carr2[leftIdx]='A';
                leftVisit=visit(leftIdx,diffCnt+1,moveCnt+leftVal+i);
                carr2[leftIdx]=carr[leftIdx];
                break;
            }
        }
        // right
        for(int i=1;i<carr.length;i++){
            int rightIdx=(idx+i)% carr.length;
            int rightVal=getAlphaDist(carr2[rightIdx]);
            if(rightVal!=0){
                carr2[rightIdx]='A';
                rightVisit=visit(rightIdx,diffCnt+1,moveCnt+rightVal+i);
                carr2[rightIdx]=carr[rightIdx];
                break;
            }
        }
        return Math.min(leftVisit,rightVisit);
    }
    private int getAlphaDist(char c){
        int idx=c-'A';
        int reIdx=26-idx;
        return Math.min(idx,reIdx);
    }
}
public class 조이스틱 {
    public static void main(String[] args) {
        Solution_조이스틱 sol=new Solution_조이스틱();
        System.out.println(sol.solution("JEROEN"));
    }
}