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

# 문제 원문

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

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

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

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

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

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

제한 사항

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

입출력 예

name / return

"JEROEN"	56
"JAN"	23

출처

 

# 문제 풀이

LEVEL 2 문제가 아닌 거 같다. 복잡하고 예외 케이스나 문제 지문이 부족한 부분이 생각보다 많아서 대략 3시간 동안 푼 거 같다. 수많은 시행착오를 한 후에 정답을 제출했지만 이게 정말 맞는 코드일까?라는 의구심이 남아 있을 정도다.

일단 알파뱃 자체는 26문자로 A가 스타트로 0의 값을 가지니 A-N, O-Z를 그룹을 나누어서 A를 기준으로 0~13, 1~12의 해쉬 테이블을 준비한다.(그냥 객체) 입력받은 문자열 name을 해쉬 테이블에 대입하여서 각 알파벳을 구하는데 걸리는 최소 동작치를 구한 후 해당 부분을 합해주면 이동하는 동작이 포함되지 않은 result를 구할 수 있다. 이 부분은 솔직히 10분도 안 걸린다 푸는데 이제 이동하는 동작을 구해야 하는데 문제의 지문에는 동작의 최솟값을 구한다면서 정작 문제에 안 나와있는 한번 방향을 전환하면 다시 방향 전환을 못한다는 내용 때문에 최솟값을 구하면 틀리게 된다. 정답을 구하려면 문제 분류에 나와있는 그리디 알고리즘을 활용해서 풀어야 한다(대체 문제가 왜 이따위 인지 모르겠다.) 개인적으로는 move를 구하는데 입력받은 name으로 만든 state 배열이 가진 스택, 큐 속성을 활용해서 접근을 시도했고, 기본적으로 state.length가 0 이 될 때까지 내부 요소를 각 조건에 맞게 shift나 pop 시키면서 result에 move를 더해서 그리디 방식으로 움직이는 최소 동작 값을 구했다.

 

# 솔루션 플로우

1. 알파벳 26 문자를 a = 0 기준으로 좌우로 1씩 가감하면서 해당 문자열 최솟값이 담긴 joyPad을 만든다.

2. 입력받은 name을 배열(state)로 만들면서 joyPad로 해당 알파벳 조작 값을 구한다.

3. state의 모든 값을 합한 값(알파벳 변경 동작 최솟값)의 합(result)을 구한다.

4. state배열의 모든 요소를 제거 할때 까지 모든 요소를 순회한다. 5-6

5. 현재 진행 방향에 맞는 current(shift, pop)을 구한 후 current가 A(0)가 아니고 state.length > 0이라면 result++해준다.

6. current가 A(0)이라면 이어진 A(0)를 카운팅하면서 모두 제거해준다. 7-8

7. A를 모두 제거한 후 state가 빈배열이라면 순회를 종료한다.

8. 방향전환은 한 번만 가능하므로 진행방향이 정방향인 조건 아래 A를 제거한 count 즉 정방향 진행과 역방향 진행 중 더 적은 이동을 하는 방향으로 이동한다.

9. 모든 과정을 마친후 구해진 result를 반환한다.

1. 해시 + 배열 반복을 활용한 풀이

function solution(name) {
    const joyPad = {};
    "ABCDEFGHIJKLMN".split('')
        .forEach((char, idx) => joyPad[char] = idx);
    "OPQRSTUVWXYZ".split('')
        .reverse()
        .forEach((char, idx) => joyPad[char] = idx + 1);
    const state = Array.from(name).map((char) => joyPad[char]);
    let result = state.reduce((ac, c) => ac + c);

    let flag = true;
    let idx = 0;
    while (state.length > 0) {
        const current = flag ?
            state.shift() :
            state.pop();
        if (current !== 0) {
            if (state.length > 0) {
                result++;
                idx++;
            }
        } else {
            let count = 1;
            for (; ;) {
                const pick = flag ? state[0] : state[state.length - 1];
                if (pick !== 0) break;
                flag ? state.shift() : state.pop();
                count++;
            }
            if (state.length === 0 && idx > 0) {
                break;
            }
            if (flag && count >= idx && idx !== 0) {
                flag = false;
                result += idx - 1;
                idx += idx;
                continue;
            }
            result += count;
            idx += count;
        }
    }

    return result;
}