[프로그래머스] 숫자 타자 대회

문제

코딩테스트 연습 - 숫자 타자 대회

알고리즘 문제 연습 카카오톡 친구해요! 프로그래머스 교육 카카오 채널을 만들었어요. 여기를 눌러, 친구 추가를 해주세요. 신규 교육 과정 소식은 물론 다양한 이벤트 소식을 가장 먼저 알려드립니다.

school.programmers.co.kr

문제 정리

요약

• 숫자로 이루어진 긴 문자열을 순서대로 누가 가장 빠르게 타이핑하는지 겨룹니다.
• 항상 왼손 엄지는 4에, 오른쪽 엄지는 6 두고 시작합니다.
• 엄지를 움직여 다른 숫자를 누르는데 일정 시간이 듭니다.
• 움직이는데 가중치는 다음과 같습니다.
  • 제자리 다시 누르는 경우 1.
  • 상하좌우 이동하여 누르는 경우 2.
  • 대각선으로 이동하여 누르는 경우 3.
• a에서 이동하여 b를 누를 때 위 규칙에 따라서 가중치가 최소가 되는 경로를 따라서 이동하여 누릅니다.

입력 조건

• numbers 길이 : 1 ~ 100,000
  • numbers는 아라비아 숫자로 이루어진 문자열입니다.

출력

numbers를 최소한 시간으로 타이핑을 하는 경우 가중치 합을 구하시오.

---

문제 풀이

DP 접근

완전 탐색을 한다고 했을 때 i 번째 숫자를 타이핑할 때 가능한 경우의 수는 2i입니다. 따라서 시간 복잡도는 2100,000로 완전 탐색으로는 해결할 수 없습니다.

여기서 주목해야 하는 것은 손의 위치 상태(손 모양)에 있습니다. 손 모양의 개수는 10개의 숫자 중에서 서로 다른 두 숫자를 순서 있게 선택하는 것과 같습니다. 따라서 손 모양의 개수는 10 x 9 = 90 개로 제한됩니다.

즉, 겉보기에는 2i만큼 경우의 수가 있는 것처럼 보이지만 실제로는 동일한 손 모양 상태가 반복적으로 등장하는 것을 알 수 있습니다.

따라서 i 번째 숫자를 눌렀을 때 손 모양을 기준으로 해당 손 모양까지의 최소 비용을 저장하는 DP를 통하여 중복 계산을 제거할 수 있습니다.

결과적으로 동일 상태에 대한 중복 계산이 제거되면서 시간 복잡도는 O(90N) = O(N)로 문제를 해결할 수 있습니다.

이동 비용 계산 방식

두 숫자 사이에 이동할 때는 대각선 이동이 직선 이동보다 더 효율적입니다. 따라서 이동 비용은 다음과 같이 계산할 수 있습니다.

cost = min(diffX, diffY) * 3 + abs(diffX - diffY) * 2

• diffX : 가로 방향 차이
• diffY : 세로 방향 차이
• min(diffX, diffY) : 대각선 이동 가능한 횟수.
• abs(diffX - diffY) : 남은 직선 이동 횟수.

---

풀이 코드

import java.util.*;

class Solution
{
    // 숫자의 위치 정보 초기화.
    static HashMap<Integer, int[]> loc;
    static {
        loc = new HashMap<>();

        loc.put(1, new int[]{0, 0});
        loc.put(2, new int[]{1, 0});
        loc.put(3, new int[]{2, 0});
        loc.put(4, new int[]{0, 1});
        loc.put(5, new int[]{1, 1});
        loc.put(6, new int[]{2, 1});
        loc.put(7, new int[]{0, 2});
        loc.put(8, new int[]{1, 2});
        loc.put(9, new int[]{2, 2});
        loc.put(0, new int[]{1, 3});
    }

    public int solution(String numbers) {
        int INF = 70_000_000;

        // key = 왼손 숫자 * 10 + 오른손 숫자
        // value = 비용.
        HashMap<Integer, Integer> DP = new HashMap<>();
        DP.put(46, 0); // 시작 손 위치 추가
        
        for (int i = 0; i < numbers.length(); i++) {
            int toMove = numbers.charAt(i) - 48;

            // i 번째 숫자 타이핑 했을 때 DP
            HashMap<Integer, Integer> next = new HashMap<>();

            for (Integer key: DP.keySet()) {
                int l = key / 10;
                int r = key % 10;

                // 왼손을 이동. -> 오른손이 toMove에 있으면 이동 불가.
                if (r != toMove) {
                    int before = next.getOrDefault(toMove * 10 + r, INF);
                    int value = calcValue(l, toMove) + DP.get(key);

                    if (value < before) {
                        next.put(toMove * 10 + r, value);
                    }
                }

                // 오른손을 이동. -> 왼손이 toMove에 있으면 이동 불가.
                if (l != toMove) {
                    int before = next.getOrDefault(l * 10 + toMove, INF);
                    int value = calcValue(r, toMove) + DP.get(key);

                    if (value < before) {
                        next.put(l * 10 + toMove, value);
                    }
                }
            }

            DP = next;
        }

        // 최솟값 찾기
        int ans = INF;

        for (Integer value: DP.values()) {
            if (ans > value) {
                ans = value;
            }
        }

        return ans;
    }

    /**
     * 숫자 a에서 숫자 b 으로 이동하는데 소모되는 비용
     * @param a 이동 시작 숫자
     * @param b 이동 목표 숫자
     * @return 이동 비용
     */
    public int calcValue(int a, int b) {
        if (a == b) {
            return 1;
        }

        int[] aLoc = loc.get(a);
        int[] bLoc = loc.get(b);

        int distX = Math.abs(aLoc[0] - bLoc[0]);
        int distY = Math.abs(aLoc[1] - bLoc[1]);

        int minDistance = Math.min(distX, distY);

        return minDistance * 3 + Math.abs(distY - distX) * 2;
    }
}