프로그래머스 [Lv. 3] 숫자 타자 대회 {언어 : JavaScript} [다시 풀어 보기]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/136797?language=javascript

프로그래머스

정답 코드

function solution(numbers) {
    const dictLocations = {
        "0": [3, 1], "1": [0, 0], "2": [0, 1], "3": [0, 2], "4": [1, 0],
        "5": [1, 1], "6": [1, 2], "7": [2, 0], "8": [2, 1], "9": [2, 2],
    };

    const calDist = (ax, ay, bx, by) => {
        const dx = Math.abs(ax - bx);
        const dy = Math.abs(ay - by);
        if (dx === 0 && dy === 0) {
            return 1; // 같은 위치에 있을 경우
        } else if (dx === 0 || dy === 0) {
            return 2 * (dx + dy); // 같은 행 또는 같은 열에 있을 경우
        }
        return 3 * Math.min(dx, dy) + 2 * Math.abs(dx - dy); // 대각선 이동 포함
    };

    const lenN = numbers.length;
    
    // DP 테이블 (index, 왼손 위치, 오른손 위치)
    const dp = Array.from({ length: lenN + 1 }, () => new Map());

    // 시작 위치 설정 (왼손 4, 오른손 6의 위치)
    dp[0].set("1,0,1,2", 0); // [왼손(4 위치), 오른손(6 위치)]에 총 이동 거리는 0으로 설정

    for (let index = 0; index < lenN; index++) {
        const number = numbers[index];
        const [nx, ny] = dictLocations[number];

        dp[index].forEach((total, key) => {
            const [lx, ly, rx, ry] = key.split(",").map(Number);
            const distLeft = calDist(lx, ly, nx, ny);
            const distRight = calDist(rx, ry, nx, ny);

            // 왼손이 이미 해당 위치에 있는 경우 (왼손 움직이지 않음)
            if (lx === nx && ly === ny) {
                const leftKey = `${lx},${ly},${rx},${ry}`;
                if (!dp[index+1].has(leftKey) || dp[index+1].get(leftKey) > total + 1) {
                    dp[index+1].set(leftKey, total+1);
                }
            }
            // 오른손이 이미 해당 위치에 있는 경우 (오른손 움직이지 않음)
            else if (rx === nx && ry === ny) {
                const rightKey = `${lx},${ly},${rx},${ry}`;
                if (!dp[index+1].has(rightKey) || dp[index+1].get(rightKey) > total + 1) {
                    dp[index+1].set(rightKey, total+1);
                }
            } else {
                // 왼손으로 이동하는 경우
                const leftKey = `${nx},${ny},${rx},${ry}`;
                if (!dp[index+1].has(leftKey) || dp[index+1].get(leftKey) > total + distLeft) {
                    dp[index+1].set(leftKey, total+distLeft);
                }

                // 오른손으로 이동하는 경우
                const rightKey = `${lx},${ly},${nx},${ny}`;
                if (!dp[index+1].has(rightKey) || dp[index+1].get(rightKey) > total + distRight) {
                    dp[index+1].set(rightKey, total+distRight);
                }
            }
        });
    }

    // 마지막 번호까지 이동한 후, 최소 거리를 찾기
    let answer = Infinity;
    dp[lenN].forEach((total) => {
        answer = Math.min(answer, total);
    });
    
    console.log(dp);
    console.log(dp[lenN]);
    
    return answer;
}

풀이 방법

 

1. 숫자 위치 좌표 맵(dictLocations): 각 숫자의 위치를 2차원 배열 상의 좌표로 나타낸다. 예를 들어, 숫자 1은 [0, 0], 숫자 2는 [0, 1], 숫자 5는 [1, 1]와 같은 좌표에 위치해 있다.
2. 거리 계산 함수(calDist): 두 손가락(왼손, 오른손)이 현재 위치에서 새로운 숫자 위치로 이동할 때의 거리를 계산하는 함수이다.
   • 같은 위치에 있을 경우 비용은 1이다.
   • 같은 행이나 열에 있을 경우, 이동 거리는 2 * (dx + dy)로 계산된다.
   • 대각선으로 이동할 경우에는 각 방향마다 비용이 다르며, 대각선 이동은 비용이 3으로 계산된다.
3. DP 테이블: dp[index]는 주어진 numbers 배열의 index번째 숫자까지 눌렀을 때의 상태를 저장한다. 각 상태는 손가락의 위치를 좌표로 표현하고, 그 상태까지의 최소 이동 거리를 기록한다.
4. 동적 계획법 알고리즘: 주어진 숫자를 하나씩 눌러가면서, 왼손과 오른손이 각각 그 숫자를 누르는 경우를 모두 탐색한다. 매 단계마다 최소 이동 거리를 계산하고, 다음 단계로 이동할 때 그 상태를 저장한다.
   • 왼손이 해당 숫자를 누를 경우와 오른손이 해당 숫자를 누를 경우에 대해 각각 이동 후의 상태를 기록한다.
   • 손가락이 이미 해당 위치에 있으면 이동하지 않고, 비용 1만 추가한다.

 

느낀점

• dp를 떠올리긴 했지만 어떻게 저장해야 할지 막막했다.
• 아래와 같이 저장하면 된다는 것을 배웠다.

[
  Map(1) { '1,0,1,2' => 0 },
  Map(2) { '0,1,1,2' => 3, '1,0,0,1' => 3 },
  Map(4) {
    '1,1,1,2' => 5,
    '0,1,1,1' => 5,
    '1,1,0,1' => 5,
    '1,0,1,1' => 5
  },
  Map(6) {
    '2,1,1,2' => 7,
    '1,1,2,1' => 8,
    '2,1,1,1' => 8,
    '0,1,2,1' => 7,
    '2,1,0,1' => 7,
    '1,0,2,1' => 7
  },
  Map(8) {
    '3,1,1,2' => 9,
    '2,1,3,1' => 12,
    '3,1,2,1' => 12,
    '1,1,3,1' => 10,
    '3,1,1,1' => 10,
    '0,1,3,1' => 9,
    '3,1,0,1' => 9,
    '1,0,3,1' => 9
  },
  Map(10) {
    '0,0,1,2' => 16,
    '3,1,0,0' => 11,
    '0,0,3,1' => 11,
    '2,1,0,0' => 19,
    '0,0,2,1' => 19,
    '1,1,0,0' => 17,
    '0,0,1,1' => 17,
    '0,1,0,0' => 16,
    '0,0,0,1' => 16,
    '1,0,0,0' => 16
  }
]

• 거리 계산 하는 방법도 개선 했다.

const calDist = (ax, ay, bx, by) => {
    if (ax == bx && ay == by) {
        // 같은 위치에 있는 경우
        return 1;
    } else if (ax == bx) {
        // 같은 행에 있는 경우
        return 2 * Math.abs(ay - by);
    } else if (ay == by) {
        // 같은 열에 있는 경우은 열에 있는 경우
        return 2 * Math.abs(ax - bx);
    } else {
        let [cx, cy] = [ax, ay];
        let dist = 0;
        // ax, ay를 기준으로
        // 좌상
        if (ax > bx && ay > by) {
            while (cx > bx && cy > by) {
                cx--;
                cy--;
                dist += 3;
            }
        }
        // 우상
        else if (ax > bx && ay < by) {
            while (cx > bx && cy < by) {
                cx--;
                cy++;
                dist += 3;
            }
        }
        // 좌하
        else if (ax < bx && ay > by) {
            while (cx < bx && cy > by) {
                cx++;
                cy--;
                dist += 3;
            }
        }
        // 우하
        else {
            while (cx < bx && cy < by) {
                cx++;
                cy++;
                dist += 3;
            }
        }
        dist += 2 * (Math.abs(cx - bx) + Math.abs(cy - by));
        return dist;
    }
}