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

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

프로그래머스

문제 유형

• 그리디

 

문제 풀이

이 문제는 항상 최선의 경우를 선택하는 그리디 알고리즘을 이용하여 해결할 수 있다.

문제를 해결하기 위해, 조이스틱을 상하로 움직이는 부분과 좌우로 움직이는 부분으로 나눠 구현해야 한다.

 

상하로 움직이는 부분의 경우 쉽게 구현할 수 있다.
name 을 알파벳 별로 차례로 탐색하면서 조작 횟수가 더 작은 방법을 선택하면 된다.
만약 알파벳 Z를 만든다면, A부터 Z까지 위로 25번 움직이는 방법과 아래로 1번 움직이는 방법가 존재한다.
이때는 조작횟수가 더 작은 아래로 1번 움직이는 방법을 선택하면 된다.

반면, 좌우로 움직이는 부분의 구현은 생각보다 매우 까다롭다.
한 가지 예를 들어보자.
name 이 BBBAAAAAAB로 주어졌을 때, 순서대로 알파벳을 탐색한다고 가정하자. (인덱스 : 0번 ~ 9번)
만약 오른쪽 커서만 사용한다면, 최대 9번의 조작으로 커서를 이동할 수 있다.
하지만 경우에 따라 왼쪽으로 이동하는 경우를 섞어주면 더 작은 조작횟수를 구할 수 있는데,
그 이유는 name 에 조작하지 않아도 되는 알파벳 A가 존재할 수 있기 때문이다.

위 예시에서는 알파벳 A가 연속으로 6개가 있으므로, 이를 이용해 좌, 우로 적당히 커서를 이동시켜보자.
0번부터 2번까지 2번 오른쪽으로 커서를 이동했다가 왼쪽으로 2번 커서를 이동하여 다시 처음으로 돌아온 뒤,
이후 연속하는 A가 나타나기 직전까지 왼쪽으로 커서를 1번 이동시켜 총 5번만에 커서를 이동할 수 있다.

이와 반대로 연속하는 A가 나타나기 직전까지 왼쪽으로 커서를 1번 이동했다가 오른쪽으로 1번 커서를 이동하여 다시 처음으로 돌아온다. 그런 뒤에 0번부터 2번까지 2번 오른쪽으로 커서를 이동시켜 총 4번만에 커서를 이동할 수 있다.
즉, 우, 좌 → 우, 우 → 좌 케이스 중에 더 작은 조작횟수를 선택하면 된다.

소스 코드

import java.util.*;

class Solution {

    public int solution(String name) {
        int answer = 0;
        int move = name.length() - 1;

        for (int i = 0; i < name.length(); i++) {
            char alphabet = name.charAt(i);

            answer += Math.min(alphabet - 'A', 'Z' - alphabet + 1);

            int aIndex = i + 1;
            while (aIndex < name.length() && name.charAt(aIndex) == 'A') {
                aIndex++;
            }

            move = Math.min(move, i * 2 + name.length() - aIndex);
            move = Math.min(move, (name.length() - aIndex) * 2 + i);
        }

        return answer + move;
    }
}