[JS] 숫자 타자 대회

예전에 이와 비슷한 문제를 봤던거 같은데 이번에는 조금 다르게 푼 것 같다.

 

문제를 보면 결국 왼손,오른손을 한번씩 움직이면서 모든 경우의 수를 구하는 방법이 있다. 해당 경우 케이스가 100,000 이므로

2^100,000개가 나와서 무조건 통과할 수 없을 것이라고 생각했다.

 

따라서 dp를 활용해서 중복되는 값을 지우면 된다고 생각했다.

 

중복되었다고 생각할 수 있는 값을 무엇으로 둘지 계속 고민하다가 왼손과 오른손이 곂치는 경우가 있다면 이는 중복된다고 생각할 수 있다 생각했다.

 

만약 왼손이 3 오른손이 *을 누르고 있는 경우가 중복된다면 그 이전까지의 값이 적은 값이 무조건 최종적으로 적은값이 나오기 때문이다.

 

따라서 dp를 12 * 12 사이즈로 잡고, dp[i][j]에서 i를 왼손이 누르고 있는 값 j를 오른손이 누르고 있는 값으로 두었다.

 

 

 

문제를 푸는 방식은 아래와 같다.

 

1. "1","2","#" 등 문자가 많이 나와서 이를 쉽게 처리할 수 있게 숫자로 바꿔주는 객체 key를 만들었다.

2. 숫자에서 숫자가 움직일때 필요한 거리를 계산해주는 함수를 만들었다. 이때 대각선으로 갈 수 있는 만큼의 수를 구하고 상하좌우로 갈 수 있는 만큼의 수를 구하면 쉽게 구할 수 있었다.

3. dp를 이용해서 dp에 적어진 cnt에서 왼손을 움직이는 경우와 오른손을 움직이는 경우 2개씩 새로운 dp에 저장해준다.

4. 각 단계별로 이전값이 남아있으면 안되므로 dp를 갱신해준다.

 

3-4단계를 진행할때 문제에서 한 자판에 두개의 손이 올라갈 수 없다고 되어있으니 해당 부분을 예외처리해준다.

 

 

 

function solution(numbers) {
    const key = {"1" : 0,"2":1,"3":2,"4":3,"5":4,"6":5,"7":6,"8":7,"9":8,"*":9,"0":10,"#":11}
    
    const getLen = (a,b) => {
        if (a==b) return 1
        const [aR,aC] = [~~(a/3),a%3]
        const [bR,bC] = [~~(b/3),b%3]
        const [r,c] = [Math.abs(aR-bR),Math.abs(aC-bC)]
        const [rightAngle,diagonal] = [Math.abs(r-c),Math.max(r,c)-Math.abs(r-c)]
        return 2*rightAngle+3*diagonal
    }
    
    let dp = [...Array(12)].map(_ => Array(12).fill(Infinity))
    dp[key[4]][key[6]] = 0
    for (const number of numbers){
        const n = key[number]
        const tmp = [...Array(12)].map(_ => 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){
                    tmp[i][n] = Math.min(dp[i][j] + getLen(j,n),tmp[i][n])
                    tmp[n][j] = Math.min(dp[i][j] + getLen(i,n),tmp[n][j])
                }
            }
        }
        dp = tmp
    }
    
    let ret = Infinity
    for (let i = 0 ; i < 12 ; i++){
        for (let j = 0 ; j <12 ; j++){
            ret = ret > dp[i][j] ? dp[i][j] : ret
        }
    }
    return ret
}

재밌는 dp문제였다^_^