[JS] 3Level / 연습문제 / 숫자 타자 대회

문제 설명

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

프로그래머스

 

문제 풀이 방법

이 문제를 처음 봤을 때는 BFS를 이용한 최단 기간 로직을 이용해 답을 구하는 줄 알았다.

하지만 경우의 수가 양손으로 먼저 나눠 2, number의 길이가 10만이기에 2^100000의 경우의 수가 나오기 때문에 BFS로는 시간 초과가 발생할거 같다.

그래서 이전 계산 결과를 이용하는 DP 알고리즘을 이용하기로 했다.

 

dp[i][j]에서 i는 왼손, j는 오른손의 위치를 표기하도록 하고 그곳에 할당된 값은 지금 까지 오는데 걸린 시간을 담기로 했다.

 

거리 계산은 x축과 y축의 간격을 절대 값으로 구한 뒤, 상하좌우 횟수와 대각이동 횟수를 각각 구한뒤 걸리는 시간만큼 곱한 뒤 반환한다.

 

완성된 코드

const solution = (numbers) => {
    const list = {"1": 0,"2": 1,"3": 2,"4": 3,"5": 4,"6": 5,"7": 6,"8": 7,"9": 8,"*": 9,"0": 10,"#": 11};

    const calLen = (a, b) => {
        if(a == b) return 1;
        const [ay, ax] = [~~(a/3), a % 3];
        const [by, bx] = [~~(b/3), b % 3];
        const [r, c] = [Math.abs(ay - by), Math.abs(ax - bx)];
        const [rec, cro] = [Math.abs(r - c), Math.max(r, c) - Math.abs(r - c)];
        const ret =  (2*rec) + (3*cro);
        return ret
    }
    
    let dp = Array.from({ length: 12 }, () => Array(12).fill(Infinity));
    dp[list[4]][list[6]] = 0;

    for(let num of numbers){
        const n = list[num];
        const arr = Array.from({ length: 12 }, () => Array(12).fill(Infinity));
        
        for(let i=0; i<12; i++){
            for(let j=0; j<12; j++){
                if(i === j) continue;
                if(dp[i][j] !== Infinity){
                    arr[i][n] = Math.min(dp[i][j] + calLen(j, n), arr[i][n]);
                    arr[n][j] = Math.min(dp[i][j] + calLen(i, n), arr[n][j]);
                }
            }
        }
        dp = arr;
    }
    let answer = Infinity;
    for(let i=0; i<12; i++){
        for(let j=0; j<12; j++){
            answer = answer > dp[i][j] ? dp[i][j] : answer;
        }
    }
    return answer;
}