[프로그래머스 고득점 kit]탐욕법 Level2 조이스틱

문제 설명

 

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

 

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

▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) ▶ - 커서를 오른쪽으로 이동

 

예를 들어 아래의 방법으로 JAZ를 만들 수 있습니다.

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다. - 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다. - 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다. 따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

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

 

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.

• name의 길이는 1 이상 20 이하입니다.

입출력 예

name

return

JEROEN	56
JAN	23

 

접근 방법

Level2 문제에 속한 것에 비해 나에게는 어렵게 느껴졌던 문제이다. 기본적인 아이디어는 다음과 같다.

 

1. 알파벳을 변경 시키기 위한 조이스틱 조작 횟수를 구한다.

2. 알파벳 자리 이동 횟수를 구한다.

 

1번 경우는 굉장히 쉽게 구할 수 있다. ('해당 알파벳' - 'A') 와 ('Z' - '해당 알파벳' + 1) 중 작은 것들을 모두 더하면 해결된다.

 

2번을 해결하는데 많은 시간을 소비하였다. 2번을 해결하기 위해서는 Greedy 알고리즘을 활용해야 한다.

 

이름의 모든 알파벳이 'A'가 아닐경우 최소 이동횟수는 이름의 길이 - 1이 될 것이다.

 

하지만 문제는 알파벳이 'A'은 경우가 중간에 끼어있을 때 발생한다. 이 문제를 해결할 수 있는 방법은 아래와 같다.

 

먼저 반복문을 통해 name의 알파벳 중 'A' 가 아닌 경우를 구하고, 이때 인덱스를 i라고 한다. i 이후 'A' 가 아닌 알파벳이 등장하는 인덱스를 next라고 한다. 이때 next는 진행방향 반대로 보았을때 마지막으로 'A'가 아닌 알파벳이 된다.

 

예를 들면 아래와 같다.

 

 

현재 위치가 'B'라고 했을 때, 진행 방향에서 'C'는 'B' 이후  처음으로 'A'가 아닌 알파벳이 된다. 그리고 진행 반대 방향에서 보았을 때 'C'는 'B' 이후 마지막으로 나타나는 'A'가 아닌 알파벳이 되는 것이다. 'B'에서 'C'까지 진행 반대 방향으로 이동하면 그 사이에 있는 모든 'A'가 아닌 알파벳은 수정이 가능하다. 

 

따라서 반대 진행 방향으로의 총 이동 횟수는 아래와 같다. (i에 2를 곱하는 이유는 0 ~ i 까지 왕복)

 

move = 2 * i('B의 인덱스') + name.length() - next('C'의 인덱스)

 

 

모든 'A'가 아닌 위치에서 move 값 중 최소값을 구하면 문제는 해결 된다.

 

 

소스 코드

class Solution {
    public int solution(String name) {
        int answer = 0;
        //alphabet
        for(int i=0;i<name.length();i++){
            int AtoZ = name.charAt(i) - 'A';
            int ZtoA = 'Z' - name.charAt(i) + 1;
            answer += Math.min(AtoZ, ZtoA);
        }
        //move
        int moveCnt = name.length() - 1;
        for(int i=0;i<name.length();i++){
            char ch = name.charAt(i);
            if(ch != 'A'){
                int next = i + 1;
                while(next < name.length() && name.charAt(next) == 'A'){
                    next++;
                }
                int move = 2 * i + name.length() - next;
                moveCnt = Math.min(moveCnt, move);
            }
        }
        return answer + moveCnt;
    }
}