문제 설명
nums라는 이름의 배열이 있고, 두 정수 x와 y가 범위 [x, y]를 정의한다고 가정해 보겠습니다. 이때 이 배열이 해당 범위에 포함되는 모든 정수를 빠짐없이 담고 있는지 확인하는 것이 과제입니다.
예를 들어 입력이 nums = [5, 8, 9, 6, 3, 2, 4], x = 2, y = 6이라면, 범위 [2, 6]의 모든 값인 2, 3, 4, 5, 6이 배열 안에 모두 존재하므로 출력은 True가 됩니다.
알고리즘: 부호 반전(In-place Marking) 기법
이 문제는 별도의 집합(set)이나 불린 배열을 새로 만들지 않고도, 배열 자체를 방문 여부 표시판으로 활용하는 부호 반전 기법으로 최소한의 추가 공간만 사용해 해결할 수 있습니다. 절댓값이 범위 내에 있는 원소를 발견하면, 그 값에 대응하는 인덱스 위치의 값을 음수로 뒤집어 "이 값이 존재한다"는 표시를 남기는 방식입니다.
구체적인 단계는 다음과 같습니다.
temp_range := y - x로 범위의 크기를 구합니다.- i를 0부터 nums의 길이까지 순회합니다.
- |nums[i]|가 x 이상 y 이하이면:
- z := |nums[i]| - x 로 값을 인덱스로 변환합니다.
- nums[z] > 0이면 nums[z] := -nums[z]로 부호를 반전시켜 방문을 표시합니다.
- cnt := 0으로 초기화한 뒤, i를 0부터 temp_range까지 순회합니다.
- i가 nums의 길이보다 크거나 같으면 루프를 종료합니다.
- nums[i] > 0이면 아직 표시되지 않은 값이 있다는 뜻이므로 False를 반환합니다.
- 그렇지 않으면 cnt를 1 증가시킵니다.
- cnt가 temp_range + 1과 같지 않으면 False를 반환합니다.
- 모든 검사를 통과하면 True를 반환합니다.
파이썬 구현 예제
def solve(nums, x, y):
temp_range = y - x
# 범위 내 값 발견 시 해당 인덱스의 부호를 반전해 방문 표시
for i in range(0, len(nums)):
if abs(nums[i]) >= x and abs(nums[i]) <= y:
z = abs(nums[i]) - x
if nums[z] > 0:
nums[z] = nums[z] * -1
# 인덱스 0 ~ temp_range가 모두 음수인지 확인
cnt = 0
for i in range(0, temp_range + 1):
if i >= len(nums):
break
if nums[i] > 0:
return False
else:
cnt += 1
if cnt != temp_range + 1:
return False
return True
nums = [5, 8, 9, 6, 3, 2, 4]
x = 2
y = 6
print(solve(nums, x, y))
입력
[5, 8, 9, 6, 3, 2, 4], 2, 6
출력
True
복잡도 분석 및 참고 사항
이 알고리즘은 배열을 두 번만 순회하므로 시간 복잡도는 O(n)이고, 추가 배열을 사용하지 않으므로 공간 복잡도는 O(1)입니다. 다만 처리 과정에서 입력 배열의 원소 부호가 실제로 변경된다는 점에 유의해야 합니다. 원본 배열을 그대로 보존해야 하는 상황이라면, 아래처럼 집합(set)을 이용하는 방법이 더 간단하고 안전한 선택이 될 수 있습니다.
def solve_with_set(nums, x, y):
s = set(nums)
return all(v in s for v in range(x, y + 1))