풀이 방법
문제 접근 방식
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(NxM^2)
시간 복잡도 = O(NxM^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());
};
마치며
이 문제도 풀고 나서 약 30분 동안 최적화를 고민해보았는데... 별 방법이 떠오르지 않는군요.
알고리즘 스터디가 끝난 후, 동료들과 한 번 의논해보고, 최적화 방법을 내놓아봐야겠어요.
이 글이 누군가에게 도움이 되었으면 좋겠네요. 이상! 😉
.jpg)