Python으로 1부터 N까지 누락된 숫자 모두 찾기 — 선형 시간 풀이

크기가 n인 숫자 리스트 nums가 있다고 가정해 봅시다. 리스트의 모든 숫자는 [1, n] 범위 안에 있으며, 일부 값은 두 번 나타나고 어떤 값은 한 번만 나타날 수 있습니다.

이때 우리가 해야 할 일은 리스트에 존재하지 않는 [1, n] 범위의 숫자를 모두 찾아 오름차순으로 정렬하여 반환하는 것입니다. 조건은 선형 시간(O(n))과 상수 공간에 가까운 효율적인 해법을 찾는 것입니다.

문제 예시

입력이 [4, 4, 2, 2, 6, 6]이라면, 1~6 범위에서 실제로 등장한 숫자는 2, 4, 6뿐입니다. 따라서 출력은 [1, 3, 5]가 됩니다.

해결 접근 방식

이 문제는 카운팅 배열(출현 횟수 기록)을 이용해 간단하게 해결할 수 있습니다. 알고리즘의 흐름은 다음과 같습니다.

• nums의 길이 + 1 크기의 배열 arr을 만들고 모든 값을 0으로 초기화합니다.
• nums의 각 숫자 i에 대해 arr[i]의 값을 1씩 증가시킵니다. 즉, 각 숫자가 몇 번 등장했는지 기록합니다.
• 결과를 담을 빈 리스트 missing을 생성합니다.
• 인덱스 0부터 arr의 끝까지 순회하면서, arr[i]가 0이고 i가 0이 아닌 경우(즉, 한 번도 등장하지 않은 숫자)를 missing에 추가합니다.
• missing을 반환합니다.

배열을 처음부터 끝까지 순서대로 확인하기 때문에 별도의 정렬 없이도 결과가 자동으로 오름차순이 됩니다.

구현 예제

class Solution:
    def solve(self, nums):
        arr = [0]*(len(nums)+1)
        for i in nums:
            arr[i] += 1
        missing = []
        for i in range(len(arr)):
            if arr[i] == 0 and i != 0:
                missing.append(i)
        return missing

ob = Solution()
print(ob.solve([4, 4, 2, 2, 6, 6]))

입력

[4, 4, 2, 2, 6, 6]

출력

[1, 3, 5]

복잡도 분석

• 시간 복잡도: O(n) — 리스트를 두 번 순회하므로 입력 크기에 비례합니다.
• 공간 복잡도: O(n) — 길이 n+1의 카운팅 배열이 추가로 필요합니다.

참고: 추가 공간 없이 푸는 방법

만약 추가 배열 사용조차 허용되지 않는다면, 인덱스 마킹 기법을 활용할 수 있습니다. 각 숫자 v가 등장할 때마다 인덱스 |v|-1 위치의 값을 음수로 바꾸어 '등장함'을 표시하고, 마지막에 양수로 남아 있는 인덱스 + 1이 곧 누락된 숫자입니다. 이 방법은 입력 리스트 자체를 수정하지만, 시간 O(n), 공간 O(1)이라는 제약 조건을 정확히 충족합니다.