프로그래머스 Lv3 숫자타자대회

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

문제 방향을 3번이나 꺾어서 풀었다.

첫 번째 방향은 완전탐색이었으나 2의 100000승 연산으로 결국 밑에 5개 케이스가 시간초과가 터졌고

두 번째 방향은 그리디였다. 왼손 오른손에서 가장 가까운 곳을 선택하고 같을 때는 왼손 클릭, 오른손 클릭 두 번의 케이스를 다 해결하는 방식이었다. -> 하지만 이 또한 완벽한 그리디가 아니었고 5개의 시간초과와 2개의 케이스에서 오류가 발생했다. 

 

결국 마지막으로 DP를 활용해야 했고 

숫자의 개수 10 

왼손 오른손 실행 하므로 10 * 10

그리고 numbers의 길이가 100000이었으므로 10 * 10 * 100000번의 실행을 한다.

O(1억) == 1초 이기에 1초 연산이 가능했다.

 

 

    static final int costs[][] = {  { 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 }};

숫자번호를 [START][END]로 배열인덱스에 맞게 거리에 대한 값을 넣어 따로 거리를 계산하는 로직을 만들지 않고 상수화했다.

 

DP의 배열은 [NUMBER길이][왼쪽위치][오른쪽위치]로 생성했고

        int[][][] arr = new int[numArr.length+1][10][10];

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                Arrays.fill(arr[i][j], M);
            }
        }
        arr[0][4][6] = 0;

 

초기값은 왼손은 4번, 오른손은 6번이므로 초기화 세팅을 해주었다.

 

그 이후 dp 연산을 시작하는 데 두 개의 조건에 맞게 진행해야 한다.

1. 왼손 오른손이 둘 다 같은 번호를 클릭할 때

2. 왼손 오른손 중 클릭할 번호에 이미 위치 했을 때

이에 대한 조건을 두어 맨 마지막까지 진행했다.

 

  for (int idx = 0; idx < numArr.length; idx++) {
            int [][] nextArr = arr[idx+1];
            int [][] nowArr = arr[idx];
            int target = Integer.parseInt(numArr[idx]);
            for (int l = 0; l < 10; l++) {
                for (int r = 0; r < 10; r++) {
                    if (nowArr[l][r] == M) continue;
                    if (l == target){
                        nextArr[l][r] = Math.min(nextArr[l][r],nowArr[l][r] + 1); 
                        continue;
                    }
                    if (r == target){
                        nextArr[l][r] = Math.min(nextArr[l][r],nowArr[l][r] + 1); 
                        continue;
                    }
                    if (target != l) {
                        nextArr[target][r] = Math.min(nextArr[target][r],nowArr[l][r]+costs[l][target]);
                    }
                    
                    if (target != r) {
                        nextArr[l][target] = Math.min(nextArr[l][target],nowArr[l][r]+costs[r][target]);                   
                    }
                }
            }
        }