제한 점프로 모을 수 있는 최대 신호 점수

자바스크립트 코딩테스트 문제로 monotonic-deque 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today hard monotonic-deque 함수명: solution 제한 시간: 400ms

일렬로 놓인 신호 증폭기 배열 signals가 있습니다. 시작점은 배열의 왼쪽 바깥(아직 어떤 칸에도 서지 않은 상태)이며, 한 번에 1칸 이상 maxJump칸 이하만큼 앞으로 점프할 수 있습니다.

점프해서 어떤 칸 i에 착지하면 signals[i]만큼 점수를 얻거나 잃습니다. 마지막에는 배열의 오른쪽 바깥으로 빠져나가면 되며, 배열 밖으로 나가는 마지막 점프도 길이가 maxJump 이하여야 합니다.

이때, 규칙을 지키면서 배열을 통과할 때 얻을 수 있는 최대 총 점수를 반환하세요.

제한사항

1 <= signals.length <= 200,000
1 <= maxJump <= 200,000
-1,000,000 <= signals[i] <= 1,000,000
시작점은 배열 바깥의 가상 위치 -1이라고 생각해도 됩니다.
시작점에서는 점수를 얻지 않습니다.
마지막 칸에 반드시 착지할 필요는 없습니다.
어떤 칸 i에 도달하려면 직전 위치 j가 i - maxJump <= j <= i - 1 이어야 합니다.
배열 밖으로 나가려면 어떤 마지막 착지 위치 j에서 n - j <= maxJump를 만족해야 합니다. 시작점에서 바로 배열 밖으로 나가는 것은 불가능합니다.

예시

입력: signals = [4, -2, 7, -3, 5], maxJump = 2 → 출력: 16
- 0 -> 2 -> 4에 착지하면 4 + 7 + 5 = 16입니다.
입력: signals = [-5, 10, -1, -1, 20], maxJump = 3 → 출력: 30
- 1 -> 4에 착지하면 10 + 20 = 30입니다.
입력: signals = [8, -100, -100, 9], maxJump = 3 → 출력: 17
- 0 -> 3에 착지한 뒤 밖으로 나가면 8 + 9 = 17입니다.

힌트

dp[i]를 i번 칸에 마지막으로 착지했을 때 얻을 수 있는 최대 점수라고 정의해 보세요.
그러면 dp[i] = signals[i] + max(dp[j]) 형태가 되는데, 여기서 j는 최근 maxJump칸 안의 위치들입니다.
매 칸마다 그 구간의 최댓값을 다시 찾으면 느립니다. 값이 큰 후보만 남기는 단조 deque를 떠올려 보세요.

해설

직접 점화식을 세우면 다음과 같습니다.

시작점은 가상 위치 -1
i번 칸에 도달하려면 직전 위치는 i - maxJump부터 i - 1 사이여야 합니다.
따라서

DP[i] = signals[i] + max(bestStart, DP[i - maxJump], ..., DP[i - 1])

여기서 bestStart는 시작점에서 한 번에 올 수 있는 칸들(i < maxJump)에 대해 사용할 수 있는 값 0입니다.

문제는 각 i마다 직전 maxJump개 칸의 최댓값을 다시 구하면 O(n * maxJump)가 된다는 점입니다. signals.length가 최대 200,000이므로 너무 느립니다.

그래서 단조 deque(monotonic deque) 를 사용합니다.

1. deque에 무엇을 넣나?

[index, dpValue] 형태의 후보를 넣습니다.

deque는 항상 dpValue가 앞에서 뒤로 갈수록 감소하도록 유지합니다. 그러면 맨 앞 원소가 언제나 현재 윈도우에서의 최댓값 후보가 됩니다.

2. 현재 칸에 쓸 수 없는 후보 제거

현재 위치가 i일 때, i - maxJump보다 작은 인덱스는 너무 멀어서 더 이상 직전 위치가 될 수 없습니다. 이 후보들을 deque 앞에서 제거합니다.

3. 현재 칸의 dp 계산

현재 칸 i에 올 수 있는 최고 점수는:

시작점에서 바로 올 수 있으면 0
아니면 deque 맨 앞의 dpValue
둘 다 가능하면 더 큰 값

즉,

bestPrev = max(시작점 사용 가능 여부에 따른 0, deque.front.dpValue)
dp[i] = signals[i] + bestPrev

4. 현재 dp를 deque에 삽입

새로 계산한 dp[i]보다 작거나 같은 값은 앞으로도 최댓값 후보가 될 가능성이 낮습니다. 왜냐하면 현재 인덱스가 더 뒤쪽에 있어서 유효 기간도 더 길기 때문입니다. 그래서 deque 뒤에서부터 dpValue <= dp[i]인 원소를 제거한 뒤 현재 원소를 넣습니다.

5. 정답은 마지막 n-maxJump … n-1 구간의 최고값

배열 밖으로 나가려면 마지막 착지 위치 j가 n - j <= maxJump를 만족해야 합니다. 즉 마지막 maxJump칸 안의 어느 위치에서든 탈출할 수 있습니다.

따라서 정답은 dp[j]들 중 j >= n - maxJump인 값의 최댓값입니다.

왜 O(n)인가?

각 인덱스는 deque에 한 번 들어가고 한 번만 나옵니다. 그래서 전체 시간 복잡도는 O(n), 추가 공간 복잡도는 O(n)(dp 저장 시) 또는 O(maxJump) 수준으로 관리할 수 있습니다.

예시 signals = [4, -2, 7, -3, 5], maxJump = 2를 보면:

dp[0] = 4
dp[1] = -2 + max(0, 4) = 2
dp[2] = 7 + max(4, 2) = 11
dp[3] = -3 + max(2, 11) = 8
dp[4] = 5 + max(11, 8) = 16

마지막 2칸 안에서 탈출 가능하므로 dp[3], dp[4] 중 최댓값인 16이 정답입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과