Find All Numbers Disappeared in an Array — 음수 마킹으로 `O(n)`/`O(1)` 누락 숫자 찾기

배열에서 사라진 숫자 찾기, 어떤 문제인가요?

LeetCode 448번 문제는 이렇게 주어집니다.

길이가 n인 정수 배열 nums가 주어집니다. 각 값은 1 이상 n 이하입니다. 1부터 n까지의 정수 중 nums에 나타나지 않은 모든 숫자를 반환하세요.

예시는 이렇습니다.

• nums = [4,3,2,7,8,2,3,1] → [5,6]
• nums = [1,1] → [2]

제약은 다음과 같습니다.

• n == nums.length
• 1 <= n <= 10^5
• 1 <= nums[i] <= n

이 문제의 핵심은 값의 범위가 배열 길이와 정확히 연결되어 있다는 점입니다. 값 x는 인덱스 x - 1로 바꿔 볼 수 있습니다. 이 글에서는 모든 후보를 매번 찾는 완전 탐색부터, 존재 여부 배열을 쓰는 풀이, 마지막으로 원본 배열의 부호를 이용해 O(n) 시간과 O(1) 추가 공간으로 푸는 방법까지 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

값 범위를 인덱스로 바꾸기

배열 길이가 n이고 값도 1..n 범위에만 있습니다.

값:      1  2  3  4  5  6  7  8
인덱스:  0  1  2  3  4  5  6  7

그래서 어떤 값 x가 등장했다는 사실은 nums[x - 1] 위치에 표시할 수 있습니다.

예를 들어 4가 등장했다면 인덱스 3을 표시합니다. 8이 등장했다면 인덱스 7을 표시합니다. 모든 값을 처리한 뒤 표시되지 않은 인덱스가 있다면, 그 인덱스에 대응하는 숫자가 배열에 없었다는 뜻입니다.

표시되지 않은 인덱스 i
→ 숫자 i + 1이 등장하지 않음

이 관점이 최종 풀이의 출발점입니다.

Phase 1. 후보 숫자마다 전체 배열에서 찾기

가장 단순한 방법은 1부터 n까지 모든 숫자를 후보로 두고, 그 숫자가 배열 안에 있는지 매번 확인하는 것입니다.

fun findDisappearedNumbers(nums: IntArray): List<Int> {
    val answer = mutableListOf<Int>()

    for (value in 1..nums.size) {
        var found = false

        for (num in nums) {
            if (num == value) {
                found = true
                break
            }
        }

        if (!found) {
            answer.add(value)
        }
    }

    return answer
}

nums = [1,1]이라면 후보는 1, 2입니다.

• 후보 1: 배열 안에 있음
• 후보 2: 배열 안에 없음 → answer에 추가

결과는 [2]입니다.

흐름은 직관적이지만, 후보 숫자마다 배열 전체를 다시 훑습니다. 배열 길이가 n이면 시간 복잡도는 O(n^2)입니다. n이 최대 10^5이므로 최악의 경우 연산량이 너무 커집니다.

Phase 2. 존재 여부 배열에 기록하기

같은 숫자를 계속 찾지 않으려면, 한 번 순회하면서 어떤 숫자가 등장했는지 따로 기록하면 됩니다.

fun findDisappearedNumbers(nums: IntArray): List<Int> {
    val seen = BooleanArray(nums.size + 1)

    for (num in nums) {
        seen[num] = true
    }

    val answer = mutableListOf<Int>()

    for (value in 1..nums.size) {
        if (!seen[value]) {
            answer.add(value)
        }
    }

    return answer
}

nums = [4,3,2,7,8,2,3,1]을 보면 등장한 값은 이렇습니다.

등장함: 1, 2, 3, 4, 7, 8
빠짐:   5, 6

seen[5]와 seen[6]만 false로 남으므로 [5,6]을 반환합니다.

이 풀이는 배열을 두 번 훑습니다.

1. nums를 순회하며 seen[num] = true
2. 1..n을 순회하며 false인 값을 수집

시간 복잡도는 O(n)입니다. 하지만 seen 배열이 필요하므로 추가 공간은 O(n)입니다. 문제의 follow-up은 반환 배열을 제외하고 추가 공간 없이 풀 수 있는지를 묻습니다. 이 조건을 만족하려면 seen 역할을 원본 배열 안에서 해결해야 합니다.

Phase 3. 원본 배열에 음수로 방문 표시하기

값 x가 등장했는지 표시할 위치는 x - 1입니다. 이 위치의 값을 음수로 바꾸면, 별도 배열 없이 "등장함"을 표시할 수 있습니다.

fun findDisappearedNumbers(nums: IntArray): List<Int> {
    for (num in nums) {
        val index = kotlin.math.abs(num) - 1

        if (nums[index] > 0) {
            nums[index] = -nums[index]
        }
    }

    val answer = mutableListOf<Int>()

    for (i in nums.indices) {
        if (nums[i] > 0) {
            answer.add(i + 1)
        }
    }

    return answer
}

핵심 규칙은 두 가지입니다.

• num이 등장했다면 abs(num) - 1 위치를 음수로 바꿈
• 이미 음수라면 이전에 같은 값이 등장한 것이므로 그대로 둠

kotlin.math.abs(num)을 쓰는 이유는 배열을 순회하는 중에 이미 음수로 바뀐 값을 다시 만날 수 있기 때문입니다. 예를 들어 원래 값이 2였는데 앞선 단계에서 -2로 바뀌었더라도, 의미하는 값은 여전히 2입니다.

예제 nums = [4,3,2,7,8,2,3,1]을 따라가 보겠습니다.

초기: [4, 3, 2, 7, 8, 2, 3, 1]

4 등장 → index 3 표시
[4, 3, 2, -7, 8, 2, 3, 1]

3 등장 → index 2 표시
[4, 3, -2, -7, 8, 2, 3, 1]

2 등장 → index 1 표시
[4, -3, -2, -7, 8, 2, 3, 1]

7 등장 → index 6 표시
[4, -3, -2, -7, 8, 2, -3, 1]

8 등장 → index 7 표시
[4, -3, -2, -7, 8, 2, -3, -1]

2 등장 → index 1은 이미 음수라 그대로
3 등장 → index 2는 이미 음수라 그대로

1 등장 → index 0 표시
[-4, -3, -2, -7, 8, 2, -3, -1]

마지막에 양수로 남은 위치는 인덱스 4, 5입니다.

index 4 → 숫자 5가 없음
index 5 → 숫자 6이 없음

따라서 정답은 [5,6]입니다.

시간 복잡도는 두 번 순회하므로 O(n)입니다. 추가로 사용하는 것은 반복 변수와 인덱스뿐이므로 공간 복잡도는 O(1)입니다. 반환 리스트는 문제에서 요구하는 출력이므로 추가 공간 계산에서 제외합니다.

참고: 이 풀이는 nums를 직접 수정합니다. 문제는 제자리 풀이를 허용하지만, 원본 배열을 이후에도 그대로 사용해야 하는 상황이라면 복사본을 사용해야 합니다. 그러면 추가 공간은 O(n)이 됩니다.

왜 음수 마킹이 맞나요?

반복문이 끝난 뒤에는 다음 의미가 성립합니다.

nums[i] < 0  → 숫자 i + 1이 한 번 이상 등장함
nums[i] > 0  → 숫자 i + 1이 한 번도 등장하지 않음

이 의미가 가능한 이유는 입력값이 모두 양수이기 때문입니다.

• 처음에는 모든 nums[i]가 1..n 범위의 양수
• 어떤 숫자가 등장하면 대응 위치를 음수로 바꿈
• 중복 숫자는 같은 위치를 다시 보지만, 이미 음수이면 그대로 둠

즉 부호 하나만으로 등장 여부를 저장할 수 있습니다. 값 자체의 크기는 중요하지 않고, 양수인지 음수인지만 보면 됩니다.

만약 입력에 0이나 음수가 섞일 수 있었다면 이 방법은 그대로 쓸 수 없습니다. 이 문제에서는 1 <= nums[i] <= n 조건이 있으므로 안전합니다.

엣지 케이스

자주 확인해 볼 만한 입력은 이렇습니다.

입력	결과	이유
[1]	[]	1이 등장했으므로 빠진 숫자 없음
[1,1]	[2]	2가 한 번도 등장하지 않음
[2,2]	[1]	1이 한 번도 등장하지 않음
[1,2,3]	[]	모든 숫자가 등장함
[2,1,2,1]	[3,4]	1, 2만 등장함
[4,3,2,7,8,2,3,1]	[5,6]	기본 예시

특히 중복이 있는 입력을 확인해야 합니다. 중복 숫자는 같은 인덱스를 여러 번 표시하므로, 이미 음수인 값을 다시 양수로 되돌리지 않는 것이 중요합니다.

세 풀이를 다시 비교

풀이	시간	공간	특징
후보마다 전체 배열 검색	O(n^2)	O(1)	가장 직관적이지만 큰 입력에서 시간 초과
존재 여부 배열 사용	O(n)	O(n)	구현이 단순하고 원본 배열을 보존
음수 제자리 마킹	O(n)	O(1)	값 범위 1..n을 인덱스로 바꿔 원본 배열에 표시

마무리

1. 이 문제는 값의 범위가 1..n이라는 조건이 핵심입니다 — 값 x를 인덱스 x - 1로 바꿔 생각할 수 있습니다
2. 존재 여부 배열을 쓰면 O(n) 시간에 쉽게 풀 수 있습니다 — 대신 O(n) 추가 공간이 필요합니다
3. 원본 배열의 부호를 바꾸면 별도 배열 없이 등장 여부를 표시할 수 있습니다 — 처음 값이 모두 양수라는 조건을 활용합니다
4. 중복 값은 이미 음수인 위치를 다시 만나게 할 뿐입니다 — 이때 다시 부호를 뒤집지 않아야 방문 표시가 유지됩니다
5. 최종 풀이는 O(n) 시간, O(1) 추가 공간입니다 — 반환 리스트는 문제의 출력이므로 보조 공간에서 제외합니다