문제 설명
수직선 위에 여러 개의 상품이 위치해 있으며, 각 상품의 좌표는 비내림차순으로 정렬된 배열prizePositions로 주어집니다. 같은 위치에 여러 상품이 있을 수도 있습니다. 또한 정수 k가 주어지며, 이는 선택할 수 있는 두 개의 닫힌 구간 각각의 길이를 의미합니다 (즉, 구간의 길이는 정확히 k여야 함).
목표는 두 개의 길이 k인 구간을 선택하여 포함되는 상품의 수를 최대화하는 것입니다. 두 구간은 겹쳐도 되며, 각 구간은 정수 좌표를 양 끝점으로 가져야 합니다.
예를 들어, k = 2일 때 [1,3]과 [2,4]와 같은 구간을 선택할 수 있습니다.
입출력 예시
- 입력:
prizePositions = [1,1,2,2,3,3,5],k = 2 - 출력:
7 - 설명: 첫 번째 구간 [1,3]은 위치 1~3 사이의 6개 상품을 포함하고, 두 번째 구간 [3,5]는 위치 3과 5에 있는 나머지 상품을 포함하여 총 7개를 얻을 수 있습니다.
- 입력:
prizePositions = [1,2,3,4],k = 0 - 출력:
2 - 설명: k가 0이므로 구간은 단일 점입니다. 예를 들어 [3]과 [4]를 선택하면 각각 하나씩, 총 2개의 상품을 얻을 수 있습니다.
접근 방법
이 문제는 다음과 같은 세 가지 핵심 아이디어를 기반으로 해결할 수 있습니다:- 슬라이딩 윈도우 (Sliding Window): 각 위치를 오른쪽 끝점으로 하는 길이
k의 구간이 포함하는 상품 수를 계산합니다. - DP 배열 활용: 인덱스
i까지의 범위에서 하나의 구간으로 얻을 수 있는 최대 상품 수를 미리 저장합니다. - 분리된 구간 조합: 현재 보는 구간을 두 번째 구간으로 간주하고, 그 왼쪽에서 가능한 최적의 첫 번째 구간과 결합하여 전체 최댓값을 갱신합니다.
알고리즘 설계
오른쪽 포인터 r을 증가시키며 슬라이딩 윈도우를 확장하고, 왼쪽 포인터 l을 조정하여 현재 윈도우 내 모든 상품이 k 이내에 있도록 유지합니다. 즉,
prizePositions[r] - prizePositions[l] <= k
를 만족해야 합니다.
또한 dp[i]를 "인덱스 i-1까지만 고려했을 때 하나의 구간으로 얻을 수 있는 최대 상품 수"로 정의합니다. 이를 통해 현재 구간(l부터 r까지)과 그 이전 구간의 최적 해를 조합할 수 있습니다.
구현 코드
def maximize_prizes(prizePositions, k):
n = len(prizePositions)
left = 0
best_total = 0
dp = [0] * (n + 1) # dp[i]: 처음 i개 원소 중 단일 구간 최대 커버
for right in range(n):
# 현재 right를 오른쪽 끝으로 할 때,
# prizePositions[right] - prizePositions[left] <= k 만족하도록
while prizePositions[right] - prizePositions[left] > k:
left += 1
current_count = right - left + 1 # 현재 구간의 상품 수
dp[right + 1] = max(dp[right], current_count)
# 현재 구간을 두 번째 구간으로 보고,
# left 이전까지의 최적 첫 번째 구간과 조합
best_total = max(best_total, current_count + dp[left])
return best_total
코드 동작 설명
left포인터는 현재 윈도우의 시작 인덱스를 가리킵니다.current_count는 현재 구간에 포함된 상품의 수입니다.dp배열은 이전 상태의 최적 값을 저장하여 재사용합니다.best_total은current_count(두 번째 구간)과dp[left](첫 번째 구간의 최적값)의 합을 기반으로 갱신됩니다.
시간 및 공간 복잡도
- 시간 복잡도: O(n) — 각 원소는 최대 한 번씩
left와right포인터에 의해 접근됩니다. - 공간 복잡도: O(n) —
dp배열 사용
테스트 검증
주어진 예시 모두 정상 작동함을 확인하였습니다. 특히 k=0인 경우에도 각 점이 독립된 구간으로 처리되어 올바른 결과를 도출합니다.