[프로그래머스] 탐욕법 - 조이스틱 문제 풀이

오늘은 프로그래머스에서 탐욕법 문제 중 조이스틱 문제 풀이를 해보겠습니다. 부분적인 알고리즘을 도출하여 전체에 적용하면 문제가 풀리는 그런 탐욕법 알고리즘의 문제입니다. 그럼 문제 풀이를 시작하겠습니다.

 

 

프로그래머스 > 탐욕법 > 조이스틱 문제 풀이

 

 

 

 

∑ 문제 정보

• 문제명: 조이스틱
• 문제 난이도: Level 2
• 문제 푼 사람수: 11533명
• 사용 가능 언어: 11개 (JavaScript 사용)

 

 

 

∑ 문제 설명

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

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

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

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

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

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

 

 

이 문제는 조이스틱을 통해 이름을 만드는데 필요한 조이스틱 최소 조작 횟수를 구하는 문제입니다.

그럼 문제에 대해 정리해보겠습니다.

• 이름을 만드는데 필요한 조이스틱의 최소 조작 횟수 구하기
• Input
  • name: 조이스틱으로 만들어야하는 이름(string)
• Output: 조이스틱으로 name을 만들기 위한 최소 조작 횟수

 

 

 

 

∑ 제한 사항

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

 

 

• name은 알파벳 대문자로만 구성
• 1 ≤ name의 길이 ≤ 20

 

 

 

 

∑ 입출력 예

name	return
"JEROEN"	56
"JAN"	23

 

 

이 문제도 입출력 예에 대한 설명이 없으므로 간단하게 설명해보겠습니다.

• 예제 #1
  1. 먼저 맨 처음 글자인 J를 위로 9번 조작하여 만든다. ( +9 )
  2. 두번째 글자로 이동하여 E를 위로 4번 조작하여 만든다. ( +1 +4 )
  3. 세번째 글자로 이동하여 R을 아래로 9번 조작하여 만든다. ( +1 +9 )
  4. 네번째 글자로 이동하여 O를 아래로 12번 조작하여 만든다. ( +1 +12 )
  5. 다섯번째 글자로 이동하여 E를 위로 4번 조작하여 만든다. ( +1 +4 )
  6. 여섯번째 글자로 이동하여 N을 위 or 아래로 13번 조작하여 만든다. ( +1 +13)
  7. 모든 횟수를 더한다. ( = 56 )
• 예제 #2
  1. 먼저 맨 처음 글자인 J를 위로 9번 조작하여 만든다. ( +9 )
  2. 왼쪽을 눌러 마지막 글자로 이동하여 N을 위 or 아래로 13번 조작하여 만든다. ( +1 +13)
  3. 모든 횟수를 더한다. ( = 23 )

 

 

 

 

∑ 알고리즘 만들기

이번 알고리즘의 주요 포인트는 어떤 알파벳을 만드느냐에 따라 몇 번 위 or 아래로 이동해야하는지 계산하는 점과 다음 글자로 이동할 때, 오른쪽으로 이동할지 왼쪽으로 이동할지, 왼쪽과 오른쪽으로 모두 이동할지를 선택하는 점이 키포인트가 될 것입니다.

 

 

1. 오직 왼쪽으로만 이동했을 때, 오직 오른쪽으로만 이동했을 때, 좌우 모두 이동했을 때 각각 최소 이동 횟수를 구한다.
2. 조이스틱의 좌우를 통해 위치 이동 횟수의 최소값을 확인한다.
3. 모든 글자를 이동하며 글자를 완성을 위해 조이스틱 조작 횟수를 계산한다.
4. 입력 값인 name을 완성하기 위한 조이스틱 조작 횟수를 반환한다.

 

 

위에서 언급한 키포인트를 참고하여 알고리즘을 만들어보았습니다.

2번에서 위치 이동 횟수의 최소값을 구하는 방법은 계속 왼쪽만 누를지, 계속 오른쪽만 누를지, 왼쪽과 오른쪽을 함께 누를지에 대해서 가장 짧은 동선에 대한 이동 횟수를 구하면 될 것입니다.

3번에서 글자를 만들기 위해 위 or 아래로 이동하는 방향을 선택하는 것은 어느쪽으로 이동해도 같은 횟수가 들어가는 알파벳인 N을 기준으로 N보다 앞이면 위로, N보다 뒤면 아래로 이동하면 될 것입니다.

위 2, 3번 부분 디테일한 알고리즘 내용을 참고하여 코드를 구현해보겠습니다.

 

 

 

 

∑ 코드 구현

function solution(name) {
    var answer = 0;
    const N = name.length;

    // 1. 오직 왼쪽으로만 이동했을 때, 오직 오른쪽으로만 이동했을 때, 좌우 모두 이동했을 때 각각 최소 이동 횟수를 구한다.
    const midLine = (N + 1) / 2;
    const [moveLeft, moveRight, onlyLeft, onlyRight] = name.split('').reduce((prev, cur, index) => {
        if(cur !== 'A') {
            if (index < midLine) {
                prev[0] = prev[0] > index ? prev[0] : index;
            } else {
                prev[1] = prev[1] > (N - index) ? prev[1] : N - index;
            }
            if (prev[2] < index) {
                prev[2] = index;
            }
            if (index !== 0 && prev[3] === 0) {
                prev[3] = N - index;
            }
        }
        return prev;
    }, [0, 0, 0, 0]);
    
    // 2. 조이스틱의 좌우를 통해 위치 이동 횟수의 최소값을 확인한다.
    answer += Math.min(onlyLeft, onlyRight, moveLeft * 2 + moveRight, moveLeft + moveRight * 2);
   
    // 3. 모든 글자를 이동하며 글자를 완성을 위해 조이스틱 조작 횟수를 계산한다.
    for(let i = 0; i < N; i++) {
        if(name[i] < 'N') {
            answer += name[i].charCodeAt() - 'A'.charCodeAt();    
        } else {
            answer += 'Z'.charCodeAt() - name[i].charCodeAt() + 1; 
        }
        
    }
    
    // 4. 입력 값인 name을 완성하기 위한 조이스틱 조작 횟수를 반환한다.
    return answer;
}

 

 

 

 

∑ 채점 결과

 

 

이번 문제는 정확성 테스트 케이스가 무려 27개나 됩니다. 정말 다양한 케이스 시험을 통해 27개를 모두 통과하여 조이스틱 문제 풀이에서 100점을 받을 수 있었습니다. 이번 문제의 키포인트는 조이스틱 위/아래 조작을 통한 알파벳 변경과 조이스틱 좌/우 조작을 통한 최소 이동 거리 찾기였다고 생각합니다. 위와 같이 분리할 수 있는 부분을 분리하여 깊게 생각해 보는 사고를 통해 최적의 알고리즘 해결책을 찾으시기 바랍니다.