[프로그래머스 Lv3] 숫자 타자 대회 - Javascript 풀이

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

프로그래머스

---

문제

숫자 배열 numbers가 주어질 때,
왼손과 오른손의 현재 위치를 고려하여 각 숫자를 입력하는 데 드는 최소한의 이동 비용(가중치)을 구하는 문제

 

생각

numbers의 최대 길이는 100,000이므로,
각 숫자를 왼손 또는 오른손으로 누르는 모든 경우의 수를 고려하면
경우의 수가 2^100,000이 되어 완전 탐색은 불가능하다.
그래서 현재 왼손/오른손의 위치에 따라 최소 비용만을 저장해 나가는 DP를 사용하면 되겠다고 생각했다.

 

DP로 풀어야 한다는 점은 이해했지만,
실제로 어떤 상태를 테이블로 정의해야 하는지(L, R 손 위치)
그 구조를 설계하는 과정이 가장 막막했다.

 

구글링과 ChatGPT를 통해 '왼손 위치 × 오른손 위치'를 상태로 두는
DP 테이블링 방식의 단서를 얻을 수 있었다.

 

다른 사람들의 코드를 보면 다음과 같은 3차원 DP 정의를 사용한다.

DP[i][L][R]
= numbers의 i번째 숫자까지 눌렀을 때,
  왼손이 L, 오른손이 R 위치에 있을 때의 최소 비용

 

이 방식은 논리적으로 완전히 맞다.

하지만 numbers의 최대 길이가 100,000이기 때문에,

DP[100000][10][10] = 10,000,000 (천만 칸)

이라는 불필요하게 큰 메모리가 필요하게 된다.

 

실제로 DP[i]를 계산할 때 필요한 것은 바로 직전 상태인 DP[i-1] 뿐이다

DP[i] = f(DP[i-1])

 

DP[i-2], DP[i-3]과 같은 과거의 상태는 계산에 전혀 사용되지 않는다.

 

따라서 모든 i에 대한 DP 배열을 저장할 필요가 없고,

현재 상태(curr)와 다음 상태(next) 두 개의 2차원 배열만 유지하면 문제를 해결할 수 있다.

 

이 방식을 Rolling Array(롤링 배열) 기법이라고 하며,
메모리를 크게 절약하면서도 동일한 DP 로직을 수행할 수 있다.

 

DP 문제를 더 많이 풀어보면서
이런 상태 정의와 테이블링 과정에 익숙해질 필요가 있다고 느꼈다.

 

문제풀이

먼저 상태를 정의해보자.

DP[L][R]

 

: 현재까지 모든 숫자를 누른 뒤,

왼손이 L 위치, 오른손이 R 위치에 있을 때 최소 비용

 

테이블을 정의했으니 점화식을 세워보자.

 

다음 눌러야 할 숫자를 K라고 하면,

1. 왼손으로 K를 누르는 경우

DP_next[K][prevR] = min(
	DP_next[K][prevR], 
    D[prevL][prevR] + dist[prevL][K]
)

 

2. 오른손으로 K를 누르는 경우

DP_next[prevL][K] = min(
	DP_next[prevL][K], 
    D[prevL][prevR] + dist[prevR][K]
)

 

최소 비용이 되는 손의 경로는 여러 가지이므로, 

모든 L/R 조합을 고려해야한다.

 

 

 

문제 조건에 따르면 두 손가락이 동시에 같은 위치에 있을 수 없다.

따라서 i번째 숫자를 누를 때,

• 왼손으로 누른다면: 이미 오른손이 그 위치에 있으면 안 되고
• 오른손으로 누른다면: 이미 왼손이 그 위치에 있으면 안 된다

즉, 다음 두 조건을 반드시 체크해야 한다.

1) next !== R   // 왼손으로 누르려면 오른손이 그 위치가 아니어야 함
2) next !== L   // 오른손으로 누르려면 왼손이 그 위치가 아니어야 함

 

시간 복잡도는 O(N)이다.

 

코드

function solution(numbers) {
    const dist = [
        [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],
    ];
    
    const INF = Infinity
    let answer = INF;
    let cur = Array.from({length: 10}, () => 
        Array(10).fill(INF)
    )
    
    cur[4][6] = 0;
    
    for(const ch of numbers) {
        const next = Number(ch)
        const nextDP = Array.from({length: 10}, () => 
            Array(10).fill(INF)
        )
        
        for(let L=0; L<10; L++) {
            for(let R=0; R<10; R++) {
                const cost = cur[L][R]
                if ( cost === INF ) continue
                
                if ( next !== R ) {
                    const c = cost + dist[L][next]
                    if ( c < nextDP[next][R] ) nextDP[next][R] = c
                }
                
                if ( next !== L ) {
                    const c = cost + dist[R][next]
                    if ( c < nextDP[L][next] ) nextDP[L][next] = c
                }
            }
        }
        
        cur = nextDP
    }
    
    for (let L = 0; L < 10; L++) {
        for (let R = 0; R < 10; R++) {
            answer = Math.min(answer, cur[L][R]);
        }
    }
    
    return answer
    
}