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

https://programmers.co.kr/learn/courses/30/lessons/42860#

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

 

풀이

상하 이동에 대한 횟수는 쉽게 생각할 수 있습니다.

위의 그림에서 알 수 있듯, 각각의 알파벳을 나타내기 위한 이동 횟수가 'N'을 기준으로 증가하다가 감소하는 것을 알 수 있습니다.

• 'A' ~ 'N' : (문자 - 'A') 번 위로 이동
• 'M' ~ 'Z' : ('Z' - 문자 + 1) 번 아래로 이동

 

문제는 좌우 이동에 대한 횟수입니다. (저는 이게 너무 어려웠습니다)

좌우 이동의 경우엔 다음과 같은 두가지가 있습니다.

• 오른쪽으로만 순서대로 이동하는 경우 -> (len-1) 번 이동
• (오른쪽으로 가다가) 연속된 A를 만나 다시 왼쪽으로 돌아가 이동하는 경우

온 길을 다시 돌아가서 이동하는 경우가 오른쪽으로만 가는 경우(len-1) 보다 적은 이동횟수를 갖는 경우를 찾아야 합니다.

 

이 경우를 생각해봅시다. 총 길이가 10이므로 오른쪽으로만 이동한다면, len-1 = 9 번의 이동을 하게 됩니다.

그런데, 여기서 무시해도 되는 가운데의 연속된 'A'를 봐야합니다.

 

오른쪽으로 가다가 다시 왼쪽으로 이동하는 경우를 고려해봅니다.

1. 오른쪽으로 이동하다가 왼쪽으로 이동하는 경우 처음 오른쪽으로 idx(2)번 이동합니다. -> 2번 이동
2. 연속된 A를 만나고, 온길을 다시 되돌아갑니다.(왼쪽으로 idx번 이동) -> 2번 이동
3. 연속된 A가 끝나는 지점은 idx = 6일 때 입니다. 따라서 conA에 연속이 끝나 새로운 글자의 등장 위치인 7을 넣어줍니다.
4. 맨뒤에서 부터 왼쪽으로 이동하며 conA번째 글자까지 와야합니다. (len - conA)번 이동 -> 3번 이동
5. 총 이동 횟수는 2+2+3 = 7입니다. (idx + idx + len - conA)

오른쪽으로만 이동하는 경우인 9번 이동보다 적은 이동횟수를 갖게 됩니다.

 

이를 이용해서 코드를 작성해야합니다!!

(이 문제가 그리디가 맞냐는 부분에 대해서 질문하기에 논란이 많더군여,,)

 

import java.util.*;

class Solution {
    public int solution(String name) {
        int answer = 0;
        int len = name.length();
        
        int move = len-1;
        for(int i=0; i<len; i++){
            //상하 이동
            //'O'~'Z'의 경우
            if(name.charAt(i) > 'N'){
                answer += 'Z' - name.charAt(i) +1;
            }
            //'A'~'N'의 경우
            else{
                answer += name.charAt(i) - 'A';
            }
            
            int conA = i+1;
            //다음 글자부터 연속된 A가 있는 경우 되돌아가는게 빠른지 확인
            while(conA < len && name.charAt(conA) == 'A'){
                conA++;
            }
            move = Math.min(move, i+len-conA+i);
                
        }
        answer+=move;
    
        return answer;
    }
}