조이스틱

문제

프로그래머스

조이스틱을 최소로 움직여서 알파벳을 만드는 문제이다. 

처음 알파벳은 글자 수 * "A" 로 설정한다. (ex : "JAZ" 이면 처음 알파벳은 "AAA")

 

먼저 내가 문제를 풀면서 처음에 생각한 방법이다.

1. 먼저 check 배열을 통해 바꿀 알파벳을 찾는다. (A는 바꿀 필요없음)

2. 현재 위치(index = 0)에서 가장 가까운 곳을 찾고 이동한다. (왼쪽, 오른쪽)

3. 이동한 위치에서 상하로 알파벳을 최소로 이동하면서 바꿈(위, 아래)

 

2 ~ 3 반복

이에 따라 아래 코드는 내가 작성한 코드이다.

import java.util.*;
class Solution {
    private static int []targetAlphabet;
    private static boolean[]change;
    private static int answer;
    public int solution(String name) {
        targetAlphabet = new int[name.length()];
        change = new boolean[name.length()]; //true이면 바꿔야됨
        
        int numberOfChange = 0; //바꿔야 하는 알파벳 개수
        
        //1
        for(int i=0;i<targetAlphabet.length;i++){
            if(name.charAt(i)!='A'){
                change[i] = true;
                numberOfChange++; 
            }
            targetAlphabet[i] = name.charAt(i)-'A';
        }
        
        answer = 0;
        int index = 0;

        int temp = 0;
        for(int i=0;i<numberOfChange;i++){
            temp = index;
            index = findNearest(temp); //2
            answer += changeAlphabet(index); //3
        }
        return answer;
    }
    private static int findNearest(int idx){
        int frontIdx = idx;
        int backIdx = idx;
        
        int finalIdx = -1;
        while(true){
            if(change[frontIdx]){
                change[frontIdx]=false;
                finalIdx = frontIdx;
                break;
            }
            else if(change[backIdx]){
                change[backIdx]=false;
                finalIdx = backIdx;
                break;
            }
            else{
                frontIdx++;
                backIdx--;
                if(frontIdx == change.length)frontIdx = 0;
                if(backIdx < 0)backIdx = change.length-1;
                answer++;
            }
        }
        return finalIdx;
    }
    
    private static int changeAlphabet(int idx){
        int result = 0;
        int up = Math.abs(targetAlphabet[idx]);
        int down = 26 - targetAlphabet[idx];
        result = Math.min(up, down);
        return result;
    }
}

하지만 몇개가 테스트케이스 일치에 실패했고, 반례를 찾았다.

예를 들어 CCCAAAAAAY 의 경우 0번째 인덱스에서 가장 가까운 위치인 왼쪽이나 오른쪽으로 갈 수 있다.

만약 쭉 오른쪽으로 가게 되었을 경우 CCC까지 가고 다시 뒤로 가서 Y로 가게 된다.

C -> C -> C -> C -> C -> C -> Y

반면에 왼쪽으로 가게 되었을 경우 Y까지 가고 다시 앞으로 가서 C로 가게 된다.

C -> Y -> C -> C -> C

즉, 아무리 최소 거리가 왼쪽, 오른쪽 같더라도 어느 방향을 선택함에 따라 결과가 달라지게 되는 것이다.

이를 연속된 A 여부에 따라 조건을 걸었다.

 

 

따라서 다시 문제의 단계를 나누었다.

1. 알파벳을 처음부터 오른쪽 방향으로 순회

2. 하나하나 알파벳을 상, 하 조작으로 알파벳 조작

3. 좌, 우 조직으로 커서 위치 조작

---

전체 코드이다.

import java.util.*;
class Solution {
    public int solution(String name) {
        int answer = 0;
        int length = name.length();
        
        int move = length-1; //오른쪽으로 쭉 이동했을 때 좌우 이동 거리
        int index; //연속된 A를 세기 위한 변수
        for(int i=0;i<length;i++){
            answer += Math.min(name.charAt(i)-'A', 'Z'- name.charAt(i)+1); //상하 이동
            
            
            index = i+1;
            while(index < length && name.charAt(index) == 'A')index++;
            
            move = Math.min(move, i*2+length-index);
            move = Math.min(move, (length-index)*2 + i);
        }
        return answer + move;
    }
}