<Lv.3> 숫자 타자 대회 (프로그래머스 : C#)

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

📕 문제 설명

숫자 타자 대회는 동일한 자판을 이용해 숫자로만 이루어진 긴 문자열을 누가 가장 빠르게 타이핑하는지 겨루는 대회다.

민희는 두 엄지 손가락을 이용하여 타이핑한다.
(왼손 엄지 = 4, 오른손 엄지 = 6)

어떤 두 숫자를 연속으로 입력하는 시간 비용을 다음의 가중치로 분류한다.
🔸 가중치 1 : 이동하지 않고 제자리에서 다시 누르기
🔸 가중치 2: 상하좌우 인접한 숫자로 이동
🔸 가중치 3: 대각선 인접한 숫자로 이동
else: 같지 않고 인접하지 않은 숫자의 경우 위 규칙에 따라 가중치 합이 최소가 되는 경로

• Input
  숫자로 이루어진 문자열
• Output
  최소한의 시간으로 타이핑 하는 경우의 가중치 합

예제

시도 1.

처음에는 그리디 처럼 접근을 시도했다.
우선 각 타자 자판에 대해 현재 손가락이 올라가있다면 다른 타자까지 거리가 얼마나 걸리는지 구해둔다.

이후 주어진 numbers에 대해 현재 왼손과 오른손 위치 중 거리가 더 짧은 위치에서 움직이도록 진행한다. (같은 경우에는 처리가 안되어서 뭔가 잘못되었다고 생각이 들었다..)

using System;
using System.Collections.Generic;

public class Solution {
    int[,] minDistFromFingerToDest;
    public int solution(string numbers) {
        int answer = 0;
        
        Dictionary<string, int> numbersToIndex = new Dictionary<string, int>()
        {
            {"1", 0}, {"2", 1}, {"3", 2}, {"4", 3},
            {"5", 4}, {"6", 5}, {"7", 6}, {"8", 7},
             {"9", 8}, {"*", 9}, {"0", 10}, {"#", 11},   
        };
        
        // i, j => i번 finger에서 j번 dest까지 가는데 걸리는 최단 거리
        minDistFromFingerToDest = new int[12, 12];
        
        for (int i = 0; i < 4; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                SetMinDist(i, j);
            }
        }
        
        int leftThumb = 3;
        int rightThumb = 5;
        for (int i = 0; i < numbers.Length; i++)
        {
            string number = numbers[i].ToString();
            int currIndex = numbersToIndex[number];
            
            int distFromLeft = minDistFromFingerToDest[leftThumb, currIndex];
            int distFromRight = minDistFromFingerToDest[rightThumb, currIndex];
            
            // 같은거 처리 해줘야하나..?
            if (distFromLeft < distFromRight) // left가 더 짧은 경우
            {
                leftThumb = currIndex;
                answer += distFromLeft;
            }
            else
            {
                rightThumb = currIndex;
                answer += distFromRight;
            }
        }
        
        return answer;
    }
    
    void SetMinDist(int startX, int startY)
    {
        bool[,] visited = new bool[4,3];
        int[,] minDist = new int[4,3];
        for(int i = 0; i < 4; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                minDist[i, j] = 100000;
            }
        }
        int[] dX = new int[4] {-1, 1, 0, 0};
        int[] dY = new int[4] {0, 0, -1, 1};
        int[] diagonalX = new int[4] {1, 1, -1, -1};
        int[] diagonalY = new int[4] {1, -1, 1, -1};
        // queue 집어넣기 (다음 노드 x, y, dist)
        minDist[startX, startY] = 1;
        
        Queue<(int, int, int)> queue = new Queue<(int, int, int)>();
        queue.Enqueue((startX, startY, 0));
        while (queue.Count >= 1)
        {
            (int currX, int currY, int dist) = queue.Dequeue();
            minDist[currX, currY] = Math.Min(minDist[currX, currY], dist);
            
            visited[currX, currY] = true;
            // 상하좌우 (가중치 2추가)
            for (int i = 0; i < 4; i++)
            {
                int newX = currX + dX[i];
                int newY = currY + dY[i];
                
                if (newX < 0 || newY < 0 || newX >= 4 || newY >= 3) continue;
                if (visited[newX, newY]) continue;
                
                queue.Enqueue((newX, newY, dist + 2));
            }
            // 대각선 (가중치 3추가)
            for (int i = 0; i < 4; i++)
            {
                int newX = currX + diagonalX[i];
                int newY = currY + diagonalY[i];
                
                if (newX < 0 || newY < 0 || newX >= 4 || newY >= 3) continue;
                if (visited[newX, newY]) continue;
                
                queue.Enqueue((newX, newY, dist + 3));
            }
        }
        
        // i * 2 + (j + 1) 
        int startNumber = startX * 3 + (startY + 1) - 1;
        minDistFromFingerToDest[startNumber, startNumber] = 1;
        
        for (int i = 0; i < 4; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                int currNumber = i * 3 + (j + 1) - 1;
                minDistFromFingerToDest[startNumber, currNumber] =  minDist[i, j];
            }
        }
    }
}

풀이

그리디하게 접근했을 때 안되는 케이스가 있어서 결국 전체를 봐야되는 상황이었다. 완전 탐색으로는 2^100000 경우를 봐야해서 무조건 시간 초과라는 생각이 들었다. 돌아돌아 dp로 풀었다..

원래 함수로 구하는 식으로 했는데 뒤늦게 숫자만 방문한다는 것을 알고 그냥 하드코딩으로 각 최단 거리는 넣어줬다.

cost[i, j] = i번에서 j로 가는 최단 거리
dp[index, left, right] = numbers[index]에 대해 제일 작은 가중치

using System;
using System.Collections.Generic;

public class Solution {
    public int[,] cost = 
    {
        { 1, 7, 6, 7, 5, 4, 5, 3, 2, 3 },
        { 7, 1, 2, 4, 2, 3, 5, 4, 5, 6 },
        { 6, 2, 1, 2, 3, 2, 3, 5, 4, 5 },
        { 7, 4, 2, 1, 5, 3, 2, 6, 5, 4 },
        { 5, 2, 3, 5, 1, 2, 4, 2, 3, 5 },
        { 4, 3, 2, 3, 2, 1, 2, 3, 2, 3 },
        { 5, 5, 3, 2, 4, 2, 1, 5, 3, 2 },
        { 3, 4, 5, 6, 2, 3, 5, 1, 2, 4 },
        { 2, 5, 4, 5, 3, 2, 3, 2, 1, 2 },
        { 3, 6, 5, 4, 5, 3, 2, 4, 2, 1 }
    };
    
    int numberLength;
    int[,] minDistFromFingerToDest;
    int[,,] dp;
    string numbersCopy;
    Dictionary<string, int> numbersToIndex;
    public int solution(string numbers) {   
        // 누를 숫자 인덱스, 왼쪽 위치, 오른쪽 위치
        // 왼손, 오른손 누르는 경우의 수 => 다른 손가락이 올라간 위치 제외
        
        numberLength = numbers.Length;
        numbersCopy = numbers;
        dp = new int[numberLength,10,10];
        
        for (int i = 0; i < numberLength; i++)
        {
            for (int j = 0; j < 10; j++)
            {
                for (int k = 0; k < 10; k++)
                {
                    dp[i, j, k] = -1;
                }
            }
        }

        return GetMinDist(0, 4, 6);
    }
    
    int GetMinDist(int index, int left, int right)
    {
        if (index == numberLength) return 0;
        
        if (dp[index, left, right] != -1) return dp[index, left, right];
        
        int numberToIndex = numbersCopy[index] - '0';
        int result = Int32.MaxValue;
        
        if (numberToIndex != right) // 왼쪽 엄지 이동
        {
            result = Math.Min(GetMinDist(index + 1, numberToIndex, right) + cost[left, numberToIndex], result);
        }
        
        if (numberToIndex != left) // 오른쪽 엄지 이동
        {
            result = Math.Min(GetMinDist(index + 1, left, numberToIndex) + cost[right, numberToIndex], result);
        }
        
        dp[index, left, right] = result;
        
        return dp[index, left, right];
    }
}

결과