조이스틱 : 그리디 (Level2)

이번문제는 상당히 생각하기 까다로운 문제라고 생각한다. 이 문제 역시 다름 사람들의 해답을 참고하였다.

 

물론 내가 그리디 문제에 약한거 같기도 하지만, 이 문제 역시 Level2치고 어렵다는 평이 많은거 같다.

 

이 문제에서 포인트는 이동거리이다. 알파벳 상/하 이동의 경우는 아스키코드를 활용하면 차이를 이용해 쉽게 구할 수 있다.

 

이제 포인트인 이동거리에 대해 확인해보자.

 

이동거리가 최대인 경우는 그냥 쭉 오른쪽으로 이동하는 것이다 즉, name.length() -1 이 최대가 될 것이다.

 

하지만, 우리는 최소 이동거리를 구해야 하므로, AAA와 같이 변경이 필요없는 A가 나올경우, 

 

그대로 그냥 쭉 오른쪽으로 진행할 것인지, 아니면 처음 되돌아가서 뒤로 진행할 것인지 정해야한다.

 

그러므로, A가 나오게 되면, 연속된 A의 마지막 index의 다음 인덱스를 구하는게 핵심이다.

 

구한 후, 

            move = Math.min(move, (i)*2 + len-conA); // 오른쪽으로 시작 후 되돌아가는 경우
            move = Math.min(move, (len-conA)*2 + i); // 뒤부터 시작 후 앞으로 되돌아가는 경우

와 같이 비교하여 더 작은 값을 구해주면, 최소 이동거리를 구할 수 있다.

 

나는 여기서 헷갈렸던 부분이 JABAAAAAAABAAAZ와 같이 A의 연속이 2번 이상 나올경우는??? 어떻게 되는건가 했는데,

 

이 경우도 코드상 A가 나올때 마다, 되돌아갈지 안갈지를 판단하기 때문에 상관이 없는 것이었다.

 

import java.util.*;

class Solution {
    public int solution(String name) {
        int answer = 0;
        
        int move = name.length();
        int len = name.length(); // 최대 이동 거리
        
        for(int i=0; i < len; i++){
            
            // 알파벳 상/하 이동
            if(name.charAt(i) < 'N'){ // 중간이 N이므로, 각 문자 사이의 크기를 각각 구한다.
                answer += name.charAt(i) - 'A';
            }else{
                answer += 'Z' - name.charAt(i) +1;
            }
            
            // 커서 좌/우 이동
            int conA = i+1; // 연속된 A의 위치
            while(conA < len && name.charAt(conA) == 'A'){ // 연속된 A의 다음 위치 구함
                conA++;
            }
            
            move = Math.min(move, (i)*2 + len-conA); // 오른쪽으로 시작 후 되돌아가는 경우
            move = Math.min(move, (len-conA)*2 + i); // 뒤부터 시작 후 앞으로 되돌아가는 경우
        }
        answer += move;
        return answer;
    }
}