문제 설명
nums라는 요소 목록이 주어졌을 때, 모든 연속된 하위 목록(부분 배열)에 그 하위 목록 안에서 정확히 한 번만 등장하는 요소가 최소 하나씩 존재하는지 확인해야 합니다. 단, 이 문제는 선형 시간 복잡도 O(n) 안에서 해결해야 한다는 조건이 있습니다.
예를 들어 입력이 nums = [5, 10, 20, 10, 0]이라면 결과는 True입니다. nums의 모든 하위 목록 [[5], [10], [20], [10], [0], [5,10], [10,20], [20,10], [10,0], [5,10,20], [10,20,10], [20,10,0], [5,10,20,10], [10,20,10,0], [5,10,20,10,0]]에는 빈도가 1인 요소가 적어도 하나씩 존재하기 때문입니다.
해결 접근 방법
핵심 아이디어는 분할 정복(Divide and Conquer)입니다. 빈도가 1인 요소는 해당 구간을 나누는 '구분자' 역할을 합니다. 특정 구간에 빈도가 1인 요소가 전혀 없다면 False를 반환하고, 존재한다면 그 요소들을 경계로 구간을 잘라 재귀적으로 검사를 진행합니다.
구체적인 단계는 다음과 같습니다.
- has_unique(left, right) 함수를 정의합니다.
- left >= right이면(구간 길이가 1 이하이면) True를 반환합니다.
- counts := nums[left ~ right] 구간에 있는 각 요소의 빈도를 저장한 딕셔너리를 만듭니다.
- counts의 최소 빈도가 1보다 크면(모든 요소가 두 번 이상 등장하면) False를 반환합니다.
- start := left로 초기화한 뒤, index를 left부터 right까지 순회하면서 다음을 수행합니다.
- counts[nums[index]] == 1이면, has_unique(start, index - 1)의 결과가 거짓일 경우 False를 반환합니다.
- start := index + 1로 갱신하여 다음 구간의 시작점을 설정합니다.
- 마지막으로 has_unique(start, right)를 반환합니다.
- 메인 함수에서는 has_unique(0, len(nums) - 1)을 호출해 전체 결과를 얻습니다.
예제 코드
아래 구현을 통해 더 자세히 이해해 보겠습니다.
from collections import Counter
def solve(nums):
def has_unique(left, right):
if left >= right:
return True
counts = Counter(nums[left : right + 1])
if min(counts.values()) > 1:
return False
start = left
for index in range(left, right + 1):
if counts[nums[index]] == 1:
if not has_unique(start, index - 1):
return False
start = index + 1
return has_unique(start, right)
return has_unique(0, len(nums) - 1)
nums = [5, 10, 20, 10, 0]
print(solve(nums))입력
[5, 10, 20, 10, 0]
출력
True