문제

Programmers, 조이스틱

핵심

• 입력의 크기가 $20$이라 구현에 초점을 맞춘다.
• 조이스틱을 이용해 'AAA...' 문자열을 주어진 name으로 만드는 최소 연산 횟수를 구해야 한다. 조이스틱은 크게 2가지 기능이 있다. 상하로 움직여 알파벳을 변경하는 것이고, 좌우로 이동해서 'A'가 아닌 알파벳을 최소한의 움직임으로 찾아야 한다. 상하로 움직여 알파벳의 최소 변경 횟수를 찾는 것은 아래 코드와 같이 간단하게 구할 수 있다. 이 문제의 핵심은 조이스틱 최소 좌우 이동 횟수를 구하는 것이다.

ans += min(name[i] - 'A', 'Z' - name[i] + 1); // 'A'는 0번 움직이고, Z는 1번 움직인다

잘못된 그리디 풀이

• 그리디 풀이는 잘못된 명제로 접근하게 되면 될까 말까 하다 끝내 안되는 구렁텅이로 빠질 수 있다. 그리디같아 보이는 문제를 코딩테스트에서 가장 늦게 풀어야 하는지 확실하게 몸으로 깨달았다. 먼저 착각하기 쉬운 그리디 풀이를 생각해 보자. 좌우 탐색 횟수가 최소가 되려면 시작점에서 출발해 좌우로 가장 가까운 곳에 있는 'A'가 아닌 문자를 찾아내면 된다는 명제를 가지고 접근한다. 해당 명제는 매 순간 최적의 선택을 하므로 겉보기에는 타당해 보인다.

while (모든 문자가 'A'가 아니라면) {
	1. 오른쪽으로 출발 -> A가 아닌 문자 발견
    // 문자 끝에 도달했다면 0으로 이동
    // {움직인 횟수, A가 아닌 문자 위치}를 저장한다.
    
    2. 왼쪽으로 출발 -> A가 아닌 문자 발견
    // 인덱스가 음수가 되었다면 (문자열 끝 인덱스)로 이동
    // {움직인 횟수, A가 아닌 문자 위치}를 저장한다.
    
    3. 움직인 횟수가 더 적은 곳을 도착 위치로 정한다.
    // 해당 위치 문자를 'A'로 변경
    // 이동 횟수에 움직인 최소 횟수 추가
}

• 다음 예시를 생각해 보자. "BBBAAAAB"에서 먼저 첫 번째 B를 A로 변경하고 나서 두 번째 B로 이동한다. 이 경우 좌우 이동 횟수는 5번이 나온다. (3번째 B에서 마지막 B까지 3번 이동해야 하므로) 하지만 해당 예시에서 최소 좌우 이동 횟수는 4번이다. 처음 B를 A로 바꾸고, 마지막 B를 바꾼 다음 두 번째 B로 이동하는 방법이다. 즉, 처음에는 조금 손해를 보는 것 같이 보이더라도 전체적으로는 최솟값을 찾아낼 수 있다.
• 그렇다면 간단히 생각해서 왼쪽으로 이동하거나 오른쪽으로 이동하는 횟수가 같다면 뭉쳐져 있는 정도에 따라서 방향을 정하는 로직을 추가하면 안 될까? 해당 예시에선 오른쪽에는 BBB 3개가 뭉쳐져 있고, 왼쪽에는 B가 하나만 있으므로 B를 선택하면 합당해 보인다. "BBBAAABA"를 생각해보자. 처음에 있는 B를 바꾸고 왼쪽에 있는(인덱스가 음수면 문자열 끝으로 이동) 마지막 B를 바꾸는 게 합리적이다. 하지만 더 가까운 곳에 있는 두 번째 B로 이동하게 된다. 즉 명제 자체가 잘못되었다.

올바른 그리디 풀이

• 해당 문제를 greedy 적으로 접근할 때는 전체 움직임이 최소가 되는 것을 고려하여 조이스틱을 좌우로 움직여야 한다. 먼저 조이스틱의 좌우 이동 횟수는 모든 문자가 'A'가 아니라면 모두 다 거쳐야 하기 때문에 문자열 길이 - 1로 알 수 있다. 중간에 'A'가 있으면 다시 원점으로 되돌아가서 문자열 끝으로 탐색하면 탐색 횟수를 줄일 수 있는 경우가 있다. 쉬운 예를 들면 "BAB"에서 초기 좌우 이동 횟수는 2이다. 하지만 첫 번째 B를 A로 바꾸고, 오른쪽으로 2칸 이동하는 것보다 원점에서 문자열 끝으로 탐색하면 1칸 만에 마지막 B에 도달할 수 있다. 이렇게 초기 좌우 이동 횟수를 더 작은 값으로 갱신할 수 있다.
• 수식으로 나타내기 위해 시작점(i)에서 오른쪽으로 이동하면서 'A'가 아닌 점의 위치를 next라고 하자. i까지 이동한 거리와 i에서 next로 이동한 거리를 합하면 전체 이동거리가 된다. 'A'가 있을 때는 원점에서 문자열 끝으로 역방향으로 탐색하여 이동 거리가 줄어든다면 이를 최솟값으로 갱신할 수 있다. 먼저 i까지 이동한 최소 이동 거리는 다음과 같이 구할 수 있다. 시작점에서 이동한다면 i, 문자열 끝에서 이동한다면 n - next로 나타낼 수 있다. 둘 중 최솟값을 선택한다.

min(i, n - next); 

• i에서 next로 원점을 거쳐 문자열 끝으로 이동해서 탐색하는 경우는 다음과 같이 구할 수 있다.

i + n - next;

• 전체 이동거리는 다음과 같은 수식으로 표현할 수 있다. 이를 모든 점에서 원점으로 돌아가 문자열 끝에서부터 이동할 때 최소가 되는지 확인하면 된다.

min(move, min(i, n - next) + i + n - next)

개선

코드

시간복잡도

• $O(N)$

C++

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(string name) {
    int ans = 0;
    int n = name.length();
    int move = n - 1;
    for (int i = 0; i < n; ++i) {
        ans += min(name[i] - 'A', 'Z' - name[i] + 1);
        int next = i + 1;
        while (next < n && name[next] == 'A')
            ++next;
        move = min(move, min(i, n - next) + i + n - next);
    }
    ans += move;
    return ans;
}

Java

class Solution {
    public int solution(String name) {
        int ans = 0;
        int n = name.length();
        int move = n - 1;
        for (int i = 0; i < n; ++i) {
            ans += Math.min(name.charAt(i)- 'A', 'Z' - name.charAt(i) + 1);
            int next = i + 1;
            while (next < n && name.charAt(next) == 'A')
                ++next;
            move = Math.min(move, Math.min(i, n - next) + i + n - next);
        }
        ans += move;
        return ans;
    }
}