서로 다른 숫자들로 이루어진 배열이 있고, 각 숫자는 [1, N] 범위 안에 속하며, 배열의 크기는 (N-4), 중복되는 요소는 하나도 없다고 가정해 보겠습니다. 그렇다면 1부터 N까지의 숫자 중 정확히 4개가 배열에 빠져 있다는 사실을 알 수 있습니다. 이번 글에서는 이렇게 누락된 4개의 숫자를 정렬된 순서대로 찾는 방법을 살펴보겠습니다.
예를 들어 입력이 A = [2, 8, 4, 13, 6, 11, 9, 5, 10]이라면 출력은 [1, 3, 7, 12]가 됩니다.
접근 방식: 부호 표시(Sign Marking) 기법
이 문제는 정렬이나 해시 집합 없이도, 추가 메모리를 거의 사용하지 않고 해결할 수 있습니다. 핵심 아이디어는 배열 자체를 '방문 여부' 표시판처럼 활용하는 것입니다. 어떤 값 v가 등장하면 인덱스 v-1 위치의 요소 부호를 음수로 뒤집습니다. 모든 처리가 끝난 뒤에도 여전히 양수로 남아 있는 위치가 바로 누락된 숫자를 가리킵니다.
배열의 크기는 N-4이므로 N에 가까운 큰 값들은 배열 범위를 벗어납니다. 이런 값들을 처리하기 위해 크기가 4인 보조 배열 temp_arr를 따로 두고, 나머지 연산(mod)을 이용해 해당 위치를 표시합니다.
알고리즘 단계
- 모든 요소가 0인 크기 4짜리 배열 temp_arr를 생성합니다.
- i를 0부터 A의 크기까지 반복합니다.
- temp := |A[i]| (절댓값)
- temp ≤ A의 크기이면 A[temp - 1]의 부호를 반전(-1을 곱함)합니다.
- temp > A의 크기이면:
- temp mod A의 크기가 0이 아니면 temp_arr[temp mod A의 크기 - 1] = -1로 설정합니다.
- 그렇지 않으면 temp_arr[(temp mod A의 크기) + A의 크기 - 1] = -1로 설정합니다.
- i를 0부터 A의 크기까지 반복하면서 A[i] > 0이면 i + 1을 출력합니다. (배열 범위 안에서 누락된 숫자)
- i를 0부터 temp_arr의 크기까지 반복하면서 temp_arr[i] ≥ 0이면 A의 크기 + i + 1을 출력합니다. (배열 범위 밖에서 누락된 숫자)
예제 구현
아래 파이썬 코드를 통해 동작 과정을 더 잘 이해할 수 있습니다.
def find_missing_nums(A):
temp_arr = [0] * 4
for i in range(0, len(A)):
temp = abs(A[i])
if temp <= len(A):
A[temp - 1] = A[temp - 1] * (-1)
elif temp > len(A):
if temp % len(A):
temp_arr[temp % len(A) - 1] = -1
else:
temp_arr[(temp % len(A)) + len(A) - 1] = -1
for i in range(0, len(A)):
if A[i] > 0:
print(i + 1, end=" ")
for i in range(0, len(temp_arr)):
if temp_arr[i] >= 0:
print(len(A) + i + 1, end=" ")
A = [2, 8, 4, 13, 6, 11, 9, 5, 10]
find_missing_nums(A)입력
[2, 8, 4, 13, 6, 11, 9, 5, 10]
출력
1 3 7 12
복잡도 분석
시간 복잡도: O(N) — 배열을 상수 번 순회하는 선형 시간 알고리즘입니다.
공간 복잡도: O(1) — 크기가 고정된 4칸짜리 보조 배열만 사용하므로 상수 공간으로 처리됩니다.