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

문제

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

프로그래머스

조이스틱으로 알파벳 이름을 완성하려고 한다.

조이스틱은 아래와 같이 네 방향으로 이동할 수 있다.

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

알파벳 이름이 주어지면, AAA에서 시작하여 알파벳 이름을 만들 수 있는 최소 조작 횟수를 구해야 한다.

 

풀이

휴리스틱하게 생각해봤을 때, 빠른 방향을 선택하는 방법은 뭘까?

 

문자 하나 하나 세로로 조작하는 경우는 알파벳 인덱스 절반 이하는 위로 조작해주면 최소 횟수가 된다. 그렇지 않은 경우, 아래로 조작하는 것이 최소 횟수가 될 것이다. 

모든 문자에 대해 위, 아래 조작중 최소 횟수를 그리디하게 선택해 세로 조작 횟수를 알아낼 수 있다.

 

커서 조작 횟수는 어떻게 구할 수 있을까?

가로 조작인 커서의 경우, 보통 첫 번째 위치에서 오른쪽으로 커서를 이동하며 하나 하나 문자열을 조작해주면 될 것이다. 

다만, 왼쪽으로 이동하는 것이 더 빠를 수도 있다.

예제 케이스 `JAZ`의 경우, 첫 번째 문자를 조작한 뒤 마지막 문자를 조작하기 위해 오른쪽으로 이동하면 조이스틱을 2번 조작해야 하지만, 왼쪽으로 한 칸만 이동하면 최소 조작 횟수가 된다.

 

처음으로 떠올린 방법은 '이름의 길이를 절반으로 나눠서 뒤의 절반은 왼쪽으로, 앞의 절반은 오른쪽으로 조작'하는 방식이었다. 처음에는 직접 포인터를 선언해서 문자를 조작하는 코드를 구현하고자 했다. 다음 조작해야 할 문자가 절반 기준 왼쪽이면 오른쪽으로 커서를 조작하려 했으나, 첫 번째 문자인 경우는 그렇게 처리해도 되겠지만 만약 현재 커서가 중간 인덱스에 있다면...? 기준점이 없어 모든 현재 커서 위치에 대해 다른 알고리즘을 적용해야 한다.

 

때문에 절대적인 시작점을 기준으로 횟수를 계산해본다. 항상 첫 문자에서 시작하므로, 커서의 시작점을 0으로 잡고, 모든 `i`를 방향을 전환하는 인덱스로 한다. 처음 이동이 오른쪽인 경우와 왼쪽인 경우 두 가지 중 최소 이동 횟수가 커서 조작의 최소 횟수가 된다.

 

예를 들어, `BCDEFGHAZY`의 경우, `i`가 6일 때 처음 이동이 왼쪽인 경우가 최소 이동 횟수가 된다.

`B Y Z Y B C D E F G H`의 순서로 먼저 A 기준 오른쪽에 위치한 부분을 먼저 조작하는 것은 10번의 조작이 필요하다.

반면, `B C D E F G H G F E D C B Y Z` 순서로 왼쪽에 위치한 부분을 먼저 조작하면 14번의 조작이 필요해진다.

 

그렇다면 두 가지 각각의 횟수는 어떻게 계산할 수 있을까?

먼저 오른쪽 방향으로 시작하는 경우, `i`까지 이동한 뒤, 방향을 바꿔 다시 `i` 만큼 왼쪽으로 이동한 뒤, 마지막 `A`를 기준으로 오른쪽에 있는 모든 문자만큼 이동해야 한다. (`i * 2 + (이름의 길이 - 마지막 A 다음 문자 인덱스)`)

왼쪽 방향으로 시작하는 경우, 먼저 문자를 역순으로 한 번 이동한 뒤, 방향을 바꿔 마지막 `A`를 기준으로 왼쪽에 있는 모든 문자만큼 이동해야 한다. (`i + 2 * (이름의 길이 - 마지막 A 다음 문자 인덱스)`)

 

코드

function solution(name) {
    let vertCount = 0;
    let horCount = name.length - 1;
    let foundA = false;
    
    // 세로 조작 횟수 계산
    for (let i = 0; i < name.length; i++) {
        if (name[i] === 'A') foundA = true;
        const index = name[i].charCodeAt(0);
        vertCount += Math.min(index - 'A'.charCodeAt(0), 'Z'.charCodeAt(0) - index + 1);
    }
    
    // 가로 조작 횟수 계산
    if (foundA) {
        for (let i = 0; i < name.length; i++) {
            let nextIndex = i + 1;
            while (nextIndex < name.length && name[nextIndex] === 'A') {
                nextIndex++;
            }
            const right = i * 2 + (name.length - nextIndex);
            const left = i + 2 * (name.length - nextIndex);
            horCount = Math.min(horCount, left, right);
        }
    }

    return vertCount + horCount;
}