[프로그래머스] 숫자 타자 대회 (Lv.3, JavaScript)

young_pallete·2023년 1월 2일

알고리즘

Algorithm

목록 보기

30/32

풀이 방법

문제 접근 방식

Brute Force vs DP

이 역시 가장 무식한 방법인 Brute Force로 먼저 푸는 방법을 고려해봅시다.
과연 이에 대한 방법은 총 몇개일까요?

이는 다음 2가지 방법을 10만 번 한다고 할 수 있겠어요.

오른손으로 누르지 않고 왼손으로 누르는 경우
왼손으로 누르지 않고 오른손으로 누르는 경우

즉 O(2^100000)이라고 할 수 있겠죠!

이를 숫자로 환산한다면, 대략 log 2 = 0.3, 0.3 * 100000 = 약 30000
따라서 약 30000자리 수의 수가 나옵니다. 절대 풀 수 없는 경우의 수에요 😖

따라서 이 문제는 DP로 풀어야 한다는 것을 직감할 수 있어야 해요.
왜냐! 결국 이전에 내가 내린 최적의 답안에서 오른손을 택한다 vs 왼손으로 택한다로 경우의 수를 최소화할 수 있기 때문입니다.

시간복잡도와 공간복잡도를 계산해보자

그렇다면 DP로 푼다면, 시간복잡도와 공간복잡도는 어떻게 나올까요?
간단합니다. 결과적으로 다음과 같이 도출할 수 있겠어요.

N = numbers.length, M = 왼손, 오른손이 누를 수 있는 경우의 수(10)일 때
공간 복잡도 = O(N x M^2)
시간 복잡도 = O(N x M^2) = O(N)
(M은 작은 수에 해당하므로 O(N)이라고 해도 무방할 듯합니다!)

오! 비록 N=100000 이지만 거의 O(N)에 근접하므로 여유롭게 문제를 풀 수 있겠군요 😉

어떻게 DP 배열을 정의할 것인가

저는 3차원 배열로 생성해주었어요.
이유는, 이 문제는 좀 특이한 게 왼손/오른손이라는 케이스를 각각 독립적으로 유지해야 하기 때문입니다.

따라서 다음과 같이 DP 배열을 생성해줍니다.

DP[N][LEFT][RIGHT] = N번째 숫자를 누르고, 왼손이 LEFT, 오른손이 RIGHT에 위치할 때 가능한 최소값

따라서 우리가 구해야 할 값도 유추해보죠.
바로 DP[numbers.length]에 존재하는 모든 인덱스 값의 최솟값이겠죠? 😉

점화식을 어떻게 정의할 것인가.

접근 1) 결국 가중치는 정해져 있다!

이 문제를 일일이 가중치를 구해주기는 상당히 귀찮을 것 같아요.
따라서 저는 2차원 배열을 생성해주었어요. 이는 다음과 같은 값을 의미해요.

weight[A][B] = A번호에서 B번호로 이동할 때 들어가는 가중치

따라서 이를 생성해주면, 왼손이든, 오른손이든 번호가 같은 건 매한가지니, 반복해서 사용할 수 있겠죠?

접근 2) 따라서 점화식을 생성하자.

이는 이전에 풀었던 쌍둥이 빌딩 숲보다 간단합니다.
결국 제가 N번째 숫자를 눌렀을 때, 왼손이 L에 있고, 오른손이 R에 있는 경우의 값을 f(N,L,R)이라 정의하면 나올 수 있는 점화식은 다음과 같을 거에요.

직전에 다른 손이 누른 위치를 K라고 할 떄,
f(N, L, R) = Math.min(f(N-1, L, K), f(N-1, K, R))

직전에 왼손이 L에 있을 때 가능한 값의 경우 중 최솟값과
직전에 오른손이 R에 있을 때 가능한 값의 경우 중 최솟값

이중 가장 작은 값을 택하면 돼요.

🚨 예외처리를 해줍시다!

하지만 이대로 문제를 푼다면, 문제를 해결할 수 없어요.
왜냐! 이 문제에는 조건이 걸려있습니다. 아주 간사하게 말이죠.😈

단, 숫자 자판은 버튼의 크기가 작기 때문에 같은 숫자 버튼 위에 동시에 두 엄지 손가락을 올려놓을 수 없습니다. 즉, 어떤 숫자를 눌러야 할 차례에 그 숫자 위에 올려져 있는 손가락이 있다면 반드시 그 손가락으로 눌러야 합니다.

따라서 위 점화식은 모든 문제에 대한 최적의 해를 구할 수 있지만, 이 문제에는 제약조건이 있기 때문에, 왼손과 오른손이 같을 경우를 제외해주면 문제를 풀 수 있답니다.

이를 자바스크립트로는 다음과 같이 풀 수 있어요!

결과

/**
 * [x] 최소 이동 가중치 배열을 생성한다.
 * [x] DP[N][L][R]을 생성한다. 이는 CASE가 N번째인 경우 왼손이 누른 위치, 오른 손이 누른 위치를 기억한다.
 * [x] 따라서 DP[N + 1] = Math.min(DP[N][L][R], DP[N][L][R])일 것이다.
 * [x] 결과를 반환한다.
 *
 * [x] 공간 복잡도 = 11000000 (n + 1)
 * [x] 시간 복잡도 = O(N * M * 2) = 100000 * 10 * 10 = 10000000
 * [x] 따라서 문제 통과할 듯...?
 */

const weights = [
  [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 solution = (numbers) => {
  const DP = Array.from({ length: numbers.length + 1 }, () =>
    Array.from({ length: 10 }, () => new Array(10).fill(Infinity))
  );

  DP[0][4][6] = 0;

  for (let idx = 0; idx < numbers.length; idx += 1) {
    const num = numbers[idx];

    const prevDP = DP[idx];
    const nowDP = DP[idx + 1];

    for (let i = 0; i < 10; i += 1) {
      for (let j = 0; j < 10; j += 1) {
        const prevValue = prevDP[i][j];
        if (i === j || prevValue === Infinity) continue;
        
        if (nowDP[num][j] > prevValue + weights[i][num]) {
            nowDP[num][j] = prevValue + weights[i][num]
        }
          
        if (nowDP[i][num] > prevValue + weights[num][j]) {
            nowDP[i][num] = prevValue + weights[num][j]
        }
      }
    }
  }

  return Math.min(...DP[numbers.length].flat().flat());
};