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

문제

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

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

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

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

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

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

 

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

 

입출력 예

jobs	return
"JEROEN"	56
"JAN"	23
이 아래부터는 제가 임의로 추가한 테스트 케이스입니다.
"AAAA"	0
"AZAAAAAAZA"	6
"BBBAAB"	9
"BBAABAAAAB"	12
"BAABAAAAAAAAAAAAAAABA"	11
"BAABAAB"	7

---

서론

이 문제의 질문하기 게시판을 보면, 문제가 잘못된 것 아니냐는 성토가 많다. 근데 사실 문제엔 아무런 문제가 없다. 대부분이 문제를 제대로 읽지 않아서 생기는 오해인데, 이 문제에선 첫번째 알파벳에서 조이스틱을 왼쪽으로 조작하면 마지막 알파벳으로 이동할 순 있지만, 마지막 알파벳에서 조이스틱을 오른쪽으로 조작한다고 첫번째 알파벳으로는 이동할 수 없다. 대부분이 이를 고려하지 않아서 문제에 오류가 있는 것 아니냐는 의문을 제기한다. 문제에는 아무런 오류가 없으므로 이 함정에 걸리지 말도록 하자.

 

풀이에 사용할 알고리즘 구상

서론에서 언급한 함정을 염두에 둔다면, 이 문제에서 커서를 좌우로 이동할 때 조이스틱 최소한으로 조작하는 방법은 모두 다음 세 가지 경우로 귀결된다.

1. 조이스틱을 왼쪽으로만 조작하는 경우
2. 조이스틱을 오른쪽으로만 조작하는 경우
3. 조이스틱을 오른쪽으로 어느 정도 조작했다가 왼쪽으로만 조작하는 경우
   (반대의 경우는 존재하지 않는다. 위에서 언급한 함정 참조)

이렇게 조이스틱을 조작해서 커서로 좌우로 이동할 때 필요한 조이스틱 조작 횟수를 좌우 조작 횟수라고 하자.

 

다음으로 조이스틱을 상하로 조작해서 알파벳을 바꾸는 데 필요한 조이스틱 조작 횟수를 상하 조작 횟수라고 하면, 우리가 구하고자 하는 조이스틱 조작 횟수의 최솟값은 이 두 조작 횟수 모두가 최소인 경우의 값이다. 따라서 각 조작 횟수에 대해 최소인 경우를 구하는 알고리즘을 구상해야 한다.

 

먼저 보다 더 간단한 상하 조작 횟수의 최솟값을 구해보자. name의 길이가 1이라고 가정해보면 특정 알파벳에 대해 A로부터 얼마나 멀리 떨어져있는지가 해당 name에 대한 상하 조작 횟수인 것을 알 수 있다. 이 때, Z는 A로부터 1만큼 떨어진 것임을 잊지 말아야 한다. 즉, 특정 알파벳에 대한 상하 조작 횟수의 최소는 (A로부터의 거리) 또는 (Z로부터의 거리 + 1) 중 더 작은 것이 된다. 또한 name의 모든 알파벳에 대해 이 상하 조작 횟수의 수는 더 줄일 수 없으므로, 모든 알파벳의 상하 조작 횟수의 합을 구해두면 전체 name의 상하 조작 횟수의 최솟값은 쉽게 구할 수 있다.

 

상하 조작 횟수의 최솟값을 구했으니 이제 좌우 조작 횟수의 최솟값을 구하면 된다. 위에서 언급한 대로 커서를 좌우로 이동할 때 조이스틱 최소한으로 조작하는 방법은 모두 세 가지 경우로 귀결된다. 따라서 각 경우를 나누어 각 경우마다 좌우 조작 횟수의 최소가 얼마인지 구하면 된다. 나는 각 경우마다 좌우 조작 횟수의 최소를 구하기 위해, 먼저 name의 길이를 저장해두고, 각 경우마다 조이스틱이 방문하지 않는 구간의 길이를 빼는 형식으로 접근했다.

 

1. 조이스틱을 왼쪽으로만 조작하는 경우 (AAAAAAAAZZBB 같은 경우)
   이 경우는 조이스틱을 오른쪽으로 조작하면 손해인 경우다. 즉, 시작 알파벳 기준 오른쪽에 연속된 A의 개수가 왼쪽에 연속된 A의 개수보다 많아서 오른쪽으로 조작할 필요가 없다는 것이다. 따라서 시작 알파벳 기준 오른쪽에 연속된 A는 조이스틱이 방문하지 않는 구간이 된다. 이 오른쪽에 연속된 A의 길이를 name의 길이에서 빼주면 좌우 조작 횟수를 구할 수 있다.

 

1. 조이스틱을 오른쪽으로만 조작하는 경우 (ZZZZZZZAAAAA 같은 경우)
   1번 경우와 반대되는 경우다. 따라서 시작 알파벳 기준 왼쪽(문자열의 오른쪽 끝이다. 첫번째 알파벳에서 조이스틱을 왼쪽으로 조작하면 마지막 알파벳으로 이동할 수 있기 때문)에 연속된 A는 조이스틱이 방문하지 않는 구간이 된다. 이 왼쪽에 연속된 A의 길이를 name의 길이에서 빼주면 좌우 조작 횟수를 구할 수 있다.

 

1. 조이스틱을 오른쪽으로 어느 정도 조작했다가 왼쪽으로만 조작하는 경우 (BBBAABAAAAAAAAAAZA 같은 경우)
   가장 복잡한 경우다. A가 연속된 개수가 가장 많은 부분을 구하고, 이 부분 직전까지만 오른쪽으로 조작하다가 왼쪽으로 조작해서 이 부분 직후까지 도달해야 한다. 따라서, 문자열 시작부터 이 부분 직전까지의 조작 횟수의 2배와 이 직후부터 문자열 끝까지의 조작 횟수를 더하면 좌우 조작 횟수가 된다.

 

결국은 세 경우 모두 연속된 A의 개수를 기준으로 고려한다는 점을 알 수 있다. 만약에 주어진 문자열에 A가 없다면 1번 경우와 2번 경우가 동일한 값으로 최솟값을 반환하므로, 결국 모든 입력 조건을 고려해야 하는 우리로서는 이 세 경우에 대한 좌우 조작 횟수를 모두 계산하여 이들 중 최솟값을 최종적으로 반환해야 한다는 점을 알 수 있다.

 

제출 코드

function solution(name) {
    let arr = [];
    let answer = 0;

    // 조이스틱의 상하 조작 횟수 구하기
    name.split("").forEach(e => {
        let time = e.charCodeAt(0)-65;
        if (time > 13) time = 26-time;
        arr.push(time);
    });
    let length = arr.length;
    answer = arr.reduce((pre, cur) => pre + cur);

    // 조이스틱의 좌우 조작 횟수 구하기
    answer += length-1;
    //// 조이스틱을 왼쪽으로만 조작하는 경우
    let temp = answer;
    for (let i = 1; i < length; i++) {
        if (arr[i] != 0) break;
        temp--;
    }

    //// 조이스틱을 오른쪽으로만 조작하는 경우
    let temp2 = answer;
    for (let i = length-1; i > 0; i--) {
        if (arr[i] != 0) break;
        temp2--;
    }
    //// 조이스틱을 오른쪽으로 어느 정도 조작했다가 왼쪽으로만 조작하는 경우
    let temp3 = answer;
    let idx = 0;
    let curCount = 0;
    let count = 0;
    for (let i = 1; i < length; i++) {
        if (arr[i] != 0) {
            count = 0;
            continue;
        }
        count++;
        if (curCount < count) {
            idx = i;
            curCount = count;
        }
    }
    temp3 -= length-1;
    temp3 += (idx-curCount)*2;
    temp3 += length-idx-1;

    // 세 경우 중 가장 작은 경우가 좌우 조작 횟수가 최소가 된다.
    answer = Math.min(temp, temp2, temp3);
    return answer;
}