문제 개요
양의 정수로만 이루어진 배열 nums가 있다고 가정해 봅시다. 우리는 이 배열에서 중복되지 않는 고유한 요소로만 구성된 부분 배열(subarray)을 하나 선택해 제거(erase)하며, 이때 얻는 점수는 해당 부분 배열 요소들의 합입니다. 목표는 정확히 하나의 부분 배열을 제거했을 때 얻을 수 있는 최대 점수를 구하는 것입니다.
예를 들어 입력이 nums = [6,3,2,3,6,3,2,3,6]이라면 결과는 11이 됩니다. 최적의 부분 배열은 [6,3,2] 또는 [2,3,6]이며, 두 경우 모두 합이 11이기 때문입니다.
접근 방법: 슬라이딩 윈도우
이 문제는 슬라이딩 윈도우(Sliding Window) 기법으로 효율적으로 해결할 수 있습니다. 윈도우 안에는 항상 중복 없는 요소만 유지하고, 새로 추가하려는 값이 이미 윈도우에 존재한다면 해당 값의 마지막 등장 위치까지 왼쪽 경계를 이동시켜 중복을 제거합니다. 이렇게 하면 각 요소가 최대 두 번(추가 한 번, 제거 한 번)만 처리되므로 선형 시간에 문제를 해결할 수 있습니다.
알고리즘 단계
seen: 현재 윈도우에 있는 값과 그 인덱스를 저장하는 딕셔너리를 생성합니다.ans(최대 점수)와sum(현재 윈도우의 합)을 0으로 초기화합니다.- 왼쪽 경계 포인터
l을 0으로 설정합니다. - 배열의 각 인덱스
r과 값x에 대해 다음을 수행합니다:x가seen에 이미 존재하면, 해당 값의 마지막 등장 인덱스index를 가져옵니다.l <= index인 동안seen[nums[l]]을 삭제하고,sum에서nums[l]을 빼며,l을 1씩 증가시켜 중복을 해소합니다.seen[x] = r로 기록하고,sum에x를 더합니다.ans를ans와sum중 더 큰 값으로 갱신합니다.
- 모든 순회가 끝나면
ans를 반환합니다.
구현 예제
더 나은 이해를 위해 아래 파이썬 구현을 살펴보겠습니다:
def solve(nums):
seen = dict()
ans = sum = 0
l = 0
for r, x in enumerate(nums):
if x in seen:
index = seen[x]
while l <= index:
del seen[nums[l]]
sum -= nums[l]
l += 1
seen[x] = r
sum += x
ans = max(ans, sum)
return ans
nums = [6,3,2,3,6,3,2,3,6]
print(solve(nums))
입력
[6,3,2,3,6,3,2,3,6]
출력
11
복잡도 분석
- 시간 복잡도: O(n) — 각 요소는 윈도우에 한 번 추가되고 최대 한 번 제거됩니다.
- 공간 복잡도: O(n) — 최악의 경우 모든 요소가 고유하여
seen딕셔너리에 n개의 항목이 저장될 수 있습니다.