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

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

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

문제 설명

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

▲ - 다음 알파벳

▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)

◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)

▶ - 커서를 오른쪽으로 이동

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

풀이

처음 문제를 풀 때는.. 생각하기가 귀찮아서 그냥 각각의 연산을 함수로 구현해서, 선택해야 할 때(다음 알파벳 or 이전 알파벳 또는 커서 왼쪽 이동 or 오른쪽 이동) 마다 각각의 함수를 호출하여 더 작은 값을 반환한 함수의 연산을 하도록 코드를 짰다.

그런데 막상 이렇게 짜놓고 보니.. 자잘한 실수가 몇 개 있어 실수 찾느라 디버깅하는데 오히려 시간이 더 걸렸다ㅠ

(일단 코드 짜놓은게 아까워서 이걸로 풀긴 했다)

import java.util.*;
/*
아래 각각의 경우마다 최적의 선택을 해서 해를 구한다.
1. 커서를 왼쪽으로 움직일지, 오른쪽으로 움직일지
2. 알파벳을 다음 알파벳으로 움직일지, 이전 알파벳으로 움직일지
*/
class Solution {
    
    public static char cur[];
    public static int curIdx = 0;    
    
    public int down(String name){
        
        int ret = 0;
        char tmp = 'A';
        
        while(true){
            if(name.charAt(curIdx) != (char)tmp){
                tmp--;
                if(tmp < 'A'){
                    tmp += 26;
                }
            }else{
                break;
            }
            ret++;
        }
        
        return ret;
    }
    
    public int up(String name){
        
        int ret = 0;
        char tmp = 'A';
        
        while(true){
            if(name.charAt(curIdx) != (char)tmp){
                tmp++;
                if(tmp > 'Z'){
                    tmp -= 26;
                }
            }else{
                break;
            }
            ret++;
        }
        
        return ret;
        
    }
    
    public int right(char[] name, int curIdx){
        int ret = 0;
        while(true){
            curIdx++;
            ret++;
            if(curIdx >= name.length){
                curIdx -= name.length;
            }
            
            if(name[curIdx] != cur[curIdx]){
                break;
            }
        }
        return ret;
    }
    
    public int left(char[] name, int curIdx){
        int ret = 0;
        while(true){
            curIdx--;
            ret++;
            if(curIdx < 0){
                curIdx += name.length;
            }
            
            if(name[curIdx] != cur[curIdx]){
                break;
            }
        }
        
        return ret;
    }
    
    public int solution(String name) {
        int answer = 0;
        
        char[] nameArr = new char[name.length()];
        cur = new char[name.length()];
        
        for(int i=0; i<nameArr.length; i++){
            nameArr[i] = name.charAt(i);
            cur[i] = 'A';
        }

        // 현재 위치의 알파벳의 변경이 필요하다면,
        // 최적의 알파벳 변경 횟수를 찾아야 하고
        // 변경이 필요없다면
        // 현재 위치에서 가장 가까운 다음 변경대상을 찾아가야 한다.
        boolean equals = false;
        while(!equals){
            for(int i=0; i<nameArr.length; i++){
                if(i == nameArr.length - 1){
                    if(nameArr[i] == cur[i]){
                        equals = true;
                        break;
                    }
                }
                if(nameArr[i] != cur[i]){
                    equals = false;
                    break;
                }
            }
            
            if(!equals){
                // 최적의 커서위치 정함
                if(nameArr[curIdx] == cur[curIdx]){
                    int l = left(nameArr, curIdx);
                    int r = right(nameArr, curIdx);

                    if(l >= r){
                        curIdx += r;
                        if(curIdx >= name.length()){
                            curIdx -= name.length();
                        }
                        answer += r;
                        //System.out.println("R : " +r);
                    }else{
                        curIdx -= l;
                        if(curIdx < 0){
                            curIdx += name.length();
                        }
                        answer += l;
                        //System.out.println("L : " + l);
                    }
                }else{
                    // 최적의 알파벳 변경횟수
                    int u = up(name);
                    int d = down(name);

                    if(u <= d){
                        char tmp = 'A';
                        tmp += (u);
                        if(tmp > 'Z'){
                            tmp -= 26;
                        }
                        cur[curIdx] = (char)tmp;
                        answer += u;
                        //System.out.println("U : " + u);
                    }else{
                        char tmp = 'A';
                        tmp -= (d);
                        if(tmp < 'A'){
                            tmp += 26;
                        }
                        cur[curIdx] = (char)tmp;
                        answer += d;
                        //System.out.println("D : " + d);
                    }
                }
            }
            
            
        }
        
        
        return answer;
    }
}

그래서.. 좀 더 고민해서 한 번 더 풀어보기로 했다.

생각한 알고리즘은 아래와 같다.

 

1. up, down 은 A로부터의 거리와 Z+1 로부터의 거리 값 중 더 작은 값으로 결정한다.

2. left, right 은 현재 위치로부터 좌측, 우측으로 한 칸씩 이동하면서 먼저 'A'가 아닌 값이 나온 방향으로 결정한다.

 

이런 식으로 풀면서 좀 아쉬웠던 점은..

JAVA 의 STRING은 IMMUTABLE 한 데이터 타입이어서 String 원소를 하나씩 바꿔가면서 비교할 수 없었다는 것..

While 문의 조건식에 String.equals()를 썼다면.. 훨씬 깔끔하고 시간복잡도도 줄일 수 있었을 텐데,

아쉽게도 이런 방식이 불가하여 While 문 내부에서 배열을 한번 더 탐색하도록 구현하였다.

 

아.. StringBuilder 사용하는 걸 생각못했네..

다음에 추가로 StringBuilder 사용해서 더 깔끔하게 짜봐야지

import java.util.*;

class Solution {
    public int solution(String name) {
        int answer = 0;
        
        // up, down --> A 로부터의 거리와 Z로부터 거리 값 중 더 작은 값으로 결정
        // left, right --> 우측/좌측탐색하여 A가 아닌 값 먼저 나오는 걸로 결정
        //             --> 우측으로 순차탐색 시 최댓값은 name.length() - 1
        
        boolean[] visited = new boolean[name.length()];
        
        // 이미 'A' 인 경우는 안바꿔줘도 되니까.. visit check
        for(int i=0; i<name.length(); i++){
            if(name.charAt(i) == 'A') visited[i] = true;
        }
        
        int curIdx = 0;
        
        // 현재 위치가 'A'이면 left, right 결정
        // 'A'가 아니면 up, down 결정
        boolean same = false;
        while(!same){
            for(int i=0; i<visited.length; i++){
                if(visited[i] && i== visited.length-1){
                    same = true;
                    break;
                }else if(!visited[i]){
                    same = false;
                    break;
                }
            }
            if(same) break;
            
            // 현재 위치가 일치하는 경우 left/right 결정
            if(visited[curIdx]){
                // 왼쪽, 오른쪽으로 이동하면서 더 작은 값으로
                for(int mv = 1; mv < name.length(); mv++){
                    if(!visited[ (curIdx+mv) % name.length()]){
                        answer += mv;
                        curIdx = (curIdx + mv) % name.length();
                        break;
                    }else if(!visited[(curIdx-mv+name.length())%name.length()]){
                        answer += mv;
                        curIdx = (curIdx - mv + name.length())%name.length();
                        break;
                    }
                }
            }
            
            // up, down 결정
            answer += Math.min(name.charAt(curIdx) - 'A', 'Z'+1 - name.charAt(curIdx));
            visited[curIdx] = true;
            
        }
        
        
        
        return answer;
    }
}