문제 개요
숫자로 이루어진 배열 nums가 주어졌을 때, 배열의 요소들이 서로 연속적인(contiguous) 값인지 확인하는 것이 목표입니다. 즉, 배열의 값들이 중복 없이 하나씩 모두 포함되어 있고, 정렬했을 때 1씩 증가하는 형태인지 검사해야 합니다.
예를 들어 입력이 nums = [6, 8, 3, 5, 4, 7]이라면, 요소들을 정렬하면 3, 4, 5, 6, 7, 8이 되므로 결과는 True입니다.
해결 접근 방식
이 문제는 추가 배열 없이 부호 표시(sign marking) 기법을 활용하면 O(n) 시간 복잡도로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열의 길이가 1보다 작으면 연속적일 수 없으므로
False를 반환합니다. - 배열의 최솟값(min_val)과 최댓값(max_val)을 구합니다.
- (max_val - min_val + 1)이 배열의 길이와 같지 않다면 범위 내에 빠진 값이 존재하는 것이므로 즉시
False를 반환합니다. - 범위 조건이 맞다면 각 요소를 순회하며, 값 v의 인덱스는 항상 (v - min_val)로 계산할 수 있습니다. 해당 인덱스 위치의 값을 음수로 바꿔 '방문했음'을 표시하고, 이미 음수라면 중복된 값이 있는 것이므로
False를 반환합니다. - 모든 요소를 중복 없이 처리했다면
True를 반환합니다.
구현 예제
def solve(nums):
if len(nums) < 1:
return False
min_val = min(nums)
max_val = max(nums)
if max_val - min_val + 1 == len(nums):
for i in range(len(nums)):
if nums[i] < 0:
j = -nums[i] - min_val
else:
j = nums[i] - min_val
if nums[j] > 0:
nums[j] = -nums[j]
else:
return False
return True
return False
nums = [6, 8, 3, 5, 4, 7]
print(solve(nums))입력
[6, 8, 3, 5, 4, 7]
출력
True
동작 원리와 복잡도
값이 [min_val, max_val] 범위 안에 연속적으로 분포한다면, 각 값 v는 고유한 인덱스 (v - min_val)에 대응됩니다. 따라서 해당 인덱스의 부호를 반전시키는 방식으로 방문 여부를 기록할 수 있고, 같은 인덱스를 두 번 방문하게 되면 그것은 곧 중복된 값이 존재한다는 의미입니다.
- 시간 복잡도: O(n) — 배열을 한 번만 순회합니다.
- 공간 복잡도: O(1) — 입력 배열 자체를 활용하므로 추가 메모리가 필요하지 않습니다.
단, 이 방식은 원본 배열의 부호가 변경된다는 점에 유의해야 하며, 원본을 보존해야 하는 경우에는 집합(set)을 이용한 비교 방식을 대안으로 고려할 수 있습니다.