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

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

프로그래머스

---

조이스틱은 가로 또는 세로로 움직일 수 있다. 이때 가로 방향이나 세로 방향이나 회전하는 것처럼 움직인다.

• 세로: 알파벳을 A-Z 사이에서 움직일 수 있다.
• 가로: 각 자리를 이동할 수 있다.

알파벳 이름의 각 자리는 맨 처음에 A로 시작한다고 가정하며, 주어진 이름을 완성하는데 걸리는 최소 조작 회수를 구한다.

---

세로 방향

 세로 방향의 알파벳 이동은 나타내는게 별로 어렵지 않았다. 세로에서 수행할 수 있는 동작은 위로 계속 움직이거나 아래로 계속 움직이는 것뿐이므로, 위로 up 회 움직여서 특정 알파벳을 만들었다고 하면, 아래로 움직이는 경우 26 - up회 움직여서 동일한 알파벳을 만들 수 있다. 따라서 up 과 26 - up 중 더 작은 값을 움직이는 것이 최소 움직임이 된다.

for(let idx = 0; idx < l; idx++) {
    const cur = name.codePointAt(idx) - A;
    ud += Math.min(cur,26 - cur);
    if(cur) {
        nonAIdx.push(idx);
    }
}

문자열 내 모든 문자를 순회하면서 'A' 의 아스키코드 값과 현재 값의 아스키코드 값을 빼면 up(cur)이 나온다. 이 값과 26 - up(cur)을 비교하여 더 작은 값을 결과에 더하고 있다.

가로 방향

 가로 방향으로 움직이는 것이 개인적으로 너무 어려웠다. 질문들 중 알파벳이 A가 아닌 문자의 인덱스를 따로 처리할 수도 있다는 설명이 있었는데, 여기서 영감을 얻게 되어 현재 문제를 겨우 풀 수 있었다.

 현재 문제에서 A가 아닌 자리는 조이스틱 조작을 통해 다른 알파벳으로 변경해야 하므로 반드시 들려야 한다. 따라서 이러한 자리들의 인덱스를 모두 모아 배열로 구성하고, 이를 모두 순회하도록 알고리즘을 구성해야 한다. 이때 시작 지점은 A를 가지더라도 반드시 들려야 하므로 배열 내에 0이 없는 경우 따로 추가한다.

 이때 각 자리는 1) 한쪽 방향으로만 계속 움직이거나, 2) 한쪽 방향으로 움직이다 반대쪽 방향으로 움직이는 경우에만 최소 거리 후보가 될 수 있다. 특정 위치를 계속 왔다 갔다 하면 당연히 최소 거리가 될 수 없으므로 이런 경우는 제외한다.

A가 아닌 값 및 시작 지점의 인덱스 모임

 위와 같이 반드시 들려야 하는 지점들을 나열해보자. 위 그림은 배열 [0, 1, 3, 5, 11, 18]에 대응된다. 위 그림에서 0을 시작으로 제시된 모든 인덱스를 들리는 경우의 수를 고려하기 위해 거리상으로 인접한 두 점을 잡고, 모든 점을 방문하도록 화살표로 나타내보자. 이때 선택한 점 둘은 직접 연결하지 않는다.  

0, 1을 잡고 점 0에서부터 걸리는 거리를 그린 그림

위 그림은 점 0, 1을 잡고 점 0에서부터 걸리는 그림을 나타낸다. 0에서 첫번째 점인 0은 시계방향, 두번째 점인 1은 반시계 방향으로 돌았는데, 점 0에서 0까지의 거리는 당연히 0이므로 자연스럽게 반시계 방향으로의 움직임만 남았다. 이때 전체 거리를 20이라고 하면 반시계방향으로 움직인 거리는 20 - 1 = 19이다.

1, 3을 잡고 점 0에서부터 걸리는 거리를 그린 그림

 그 다음으로는 인접한 점 1, 3을 선택하고 시작점 0에서부터 걸리는 거리를 계산해보자. 0 -> 1의 거리는 1, 0 -> 3의 거리는 20 - 3 = 17이 된다.

 여기서 중요한 점은 위 그림처럼 순회하는 경우 반드시 한번은 방향을 바꿔야 한다는 점이다. 처음에 시계 방향으로 돈다고 가정하면 1에 도착했을 때 3으로 가는 길이 없으므로 해당 위치에서부터 3까지 반시계방향으로 돌아야 한다. 이 거리는 dis(0->1) * 2 + dis(0->3)이다.

 이처럼 0을 포함하지 않는 두 인접한 점의 경우 반드시 한번 방향을 바꾼다. 전체적으로 짧은 거리를 움직이기 위해서는 두 방향 중 더 짧은 방향을 왕복하고, 긴 방향으로 움직여야 한다. 위 경우에서는 0 -> 1이 더 짧은 거리였지만, 0 -> 3이 더 짧았다면 2 * dis(0->3) + dis(0->1)이 더 짧은 거리가 된다.

이후 움직일 수 있는 경우의 수들

 이와 같은 방식으로 인접한 점들을 조사하면 최소 경로가 가능한 모든 경우의 수를 구할 수 있다. 각 경로의 길이를 계산할 때마다 최소 길이를 갱신하면 for문을 순회하면서 가장 적게 움직이는 경우의 수를 도출 할 수 있게 된다.

---

코드

위와 같은 논리로 작성한 코드는 다음과 같다.

function solution(name) {
    const l = name.length;
    var lr = l - 1; // 한방향으로 쭉 갈때
    const A = 'A'.codePointAt(0);
    const nonAIdx = [];
    
    let ud = 0; // 위아래 움직임 경우의 수
    // 알파벳 만들기: 위아래 움직이는 수 계산
    for(let idx = 0; idx < l; idx++) {
        const cur = name.codePointAt(idx) - A;
        ud += Math.min(cur,26 - cur);
        if(cur) {
            nonAIdx.push(idx);
        }
    }
    // 배열에 첫번째 인덱스가 포함되지 않는 경우 추가
    if(nonAIdx.length === 0 || nonAIdx[0] != 0) {
        nonAIdx.splice(0,0,0);
    }

	//for문 순회하며 인접한 점 잡고 최소 거리 갱신하며 계산
    for(let i = 0; i < nonAIdx.length; i++) { 
        const first = nonAIdx[i]; // 첫번째 위치의 인덱스
        const last = nonAIdx[(i + 1)%nonAIdx.length]; // 다음 값의 인덱스
        
        const fd = first; // 시계방향 거리
        const ld = (l - last) % l; // 반시계방향 거리
        if(first === 0) { // 두 점에 0이 포함되는 경우 
            lr = Math.min(lr, ld); // 시계방향 도는 경우만 고려
        } else if (last === 0) {
            lr = Math.min(lr, fd); // 반시계방향 도는 경우만 고려
        } else {
            if(fd > ld) { // 시계 vs 반시계 더 짧은 거리와 비교
                lr = Math.min(lr, fd + ld * 2); 
            } else {
                lr = Math.min(lr, fd * 2 + ld);
            }
        }
    }
    
    return lr + ud; // 상하 | 좌우 움직임 더해서 반환
}

 상하 움직임은 정말 쉽게 해결할 수 있었지만, 좌우는 정말 너무 생각하기 어려운 문제였다. 그나마 해답 없이 풀 수 있어서 정말 다행이었다. 이런 발상을 실제 코딩 테스트에서 할 수 있을지는 모르겠다...