겹치지 않는 두 홍보 구간의 최대 합

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

today medium fixed-window-dp 함수명: maxTwoPromoWindows 제한 시간: 400ms

길이 k인 두 구간을 겹치지 않게 골라 합을 최대화하는 문제입니다.

문제 설명

정수 배열 nums와 양의 정수 k가 주어집니다.

길이가 정확히 k인 연속 구간 두 개를 서로 겹치지 않게 골라야 합니다. 이때 두 구간 원소 합의 총합이 최대가 되도록 하세요.

함수 maxTwoPromoWindows(nums, k)는 아래 형식으로 결과를 반환해야 합니다.

• [maxSum, leftStart, rightStart]
  • maxSum: 고른 두 구간의 합의 총합
  • leftStart: 왼쪽 구간의 시작 인덱스
  • rightStart: 오른쪽 구간의 시작 인덱스

단, 가능한 답이 여러 개라면

1. leftStart가 더 작은 조합
2. 그래도 같으면 rightStart가 더 작은 조합 을 반환하세요.

길이 k인 구간 두 개를 만들 수 없으면 null을 반환하세요.

제한사항

• 1 <= nums.length <= 200,000
• -1,000,000 <= nums[i] <= 1,000,000
• 1 <= k <= nums.length
• 두 구간은 겹치면 안 됩니다.
• 구간은 정확히 길이 k여야 합니다.

예시

• 입력: nums = [4, 5, 1, 3, 2, 8, 1, 6], k = 2 → 출력: [19, 0, 4]
• 입력: nums = [1, 2, 3, 4, 5, 6], k = 2 → 출력: [18, 2, 4]
• 입력: nums = [5, 1, 5, 1, 5, 1], k = 2 → 출력: [12, 0, 2]
• 입력: nums = [3, 9, 1], k = 2 → 출력: null

첫 번째 예시에서는 길이 2 구간 합들이 다음과 같습니다.

• 시작 0: 4 + 5 = 9
• 시작 1: 5 + 1 = 6
• 시작 2: 1 + 3 = 4
• 시작 3: 3 + 2 = 5
• 시작 4: 2 + 8 = 10
• 시작 5: 8 + 1 = 9
• 시작 6: 1 + 6 = 7

여기서 시작 0 구간 [4, 5]와 시작 4 구간 [2, 8]은 겹치지 않고 총합이 9 + 10 = 19입니다. 이보다 큰 합을 만드는 조합은 없으므로 정답은 [19, 0, 4]입니다.

힌트

• 먼저 길이 k인 모든 구간 합을 빠르게 구해 보세요.
• 어떤 오른쪽 구간을 고정했을 때, 그보다 왼쪽에서 고를 수 있는 최고 구간이 바로 떠오르면 좋습니다.
• 매번 왼쪽을 다시 전부 찾지 말고, 지금까지의 최고 왼쪽 구간을 미리 저장해 두면 됩니다.

해설

핵심은 문제를 두 단계로 나누는 것입니다.

1) 길이 k인 모든 구간 합 구하기

길이 k 구간 합을 매번 새로 더하면 느립니다. 슬라이딩 윈도우를 사용하면 모든 구간 합을 O(n)에 구할 수 있습니다.

예를 들어 windowSums[i]를

• nums[i]부터 nums[i + k - 1]까지의 합

이라고 두면, 가능한 모든 길이 k 구간을 한 번씩만 표현할 수 있습니다.

2) 각 위치까지의 최고 왼쪽 구간 미리 저장하기

이제 오른쪽 구간 시작점 r를 하나 정했다고 합시다. 그러면 왼쪽 구간은 반드시 r - k 이하에서 끝나야 하므로, 실제로는 windowSums[0 ... r - k] 중 최댓값 하나만 알면 됩니다.

이를 위해 bestLeft[i]를

• windowSums[0..i] 범위에서 가장 좋은 구간의 시작 인덱스

로 저장합니다.

좋다는 기준은

1. 구간 합이 더 큼
2. 합이 같으면 시작 인덱스가 더 작음 입니다.

그다음 오른쪽 구간 시작점 r를 k부터 끝까지 순회하면서

• 왼쪽 후보 l = bestLeft[r - k]
• 총합 windowSums[l] + windowSums[r]

을 계산하면 됩니다.

이때 정답 갱신 기준은

1. 총합이 더 큼
2. 총합이 같으면 l이 더 작음
3. 그것도 같으면 r이 더 작음 입니다.

왜 맞을까?

각 오른쪽 구간 r에 대해, 겹치지 않는 왼쪽 후보들 중 최적인 것만 보면 충분합니다. 왜냐하면 같은 r에 대해 왼쪽 구간이 더 나쁜 후보를 고를 이유가 없기 때문입니다.

즉,

• 오른쪽 구간을 하나씩 보면서
• 그 시점까지 가능한 최고 왼쪽 구간과만 조합

하면 모든 유효 조합 중 최댓값을 빠짐없이 검사하게 됩니다.

시간 복잡도

• 구간 합 계산: O(n)
• 최고 왼쪽 후보 전처리: O(n)
• 오른쪽 구간 순회: O(n)

따라서 전체 시간 복잡도는 O(n)이고, 추가 공간 복잡도는 O(n)입니다.

코드 작성

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

JavaScript 에디터 로딩 중...

커스텀 테스트

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

입력값 []

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

실행 결과

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

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.