[LeetCode] Find All Numbers Disappeared in an Array

문제

문제명: Find All Numbers Disappeared in an Array
출처: LeetCode 448

문제 설명

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

예시 입출력

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

Example 2:

Input: nums = [1,1]  
Output: [2]

제약사항

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

---

고민

문제를 처음 봤을 때 생각은 이랬다:

"아, 1부터 n까지의 숫자 중에서 빠진 것들을 찾는 문제구나!"

처음에는 정말 단순하게 생각했다. 배열을 정렬하고 순차적으로 훑으면서 빠진 숫자를 찾으면 되지 않을까?

• 뒤죽박죽으로 배치되어있는 배열 요소를 정렬을 한 후에 순차적으로 증가되지 않은 숫자를 탐색
• 증가되지 않은 요소 인덱스에 순서대로 배치해야하니 불변 배열이 아닌 가변 배열로 사용해야할 것 같다

---

해결

1. 크기 n인 Boolean 배열을 만든다 (초기값: false)
2. 주어진 배열을 순회하면서 해당 숫자에 대응하는 인덱스를 true로 마킹
3. Boolean 배열에서 false인 인덱스들이 바로 빠진 숫자들!

class Solution {
    fun findDisappearedNumbers(nums: IntArray): List<Int> {
        val n = nums.size
        val temp = BooleanArray(n)  // 초기값은 모두 false

        // 존재하는 숫자들을 true로 마킹
        for (num in nums) {
            temp[num - 1] = true  // 1-indexed를 0-indexed로 변환
        }

        val result = mutableListOf<Int>()
        // false인 인덱스들이 빠진 숫자들
        for (i in 0 until n) {
            if (!temp[i]) {
                result.add(i + 1)  // 0-indexed를 1-indexed로 변환
            }
        }

        return result
    }
}

---

결과

---

후기

원래는 [1, 2, 2, ... ]로 되는 형태의 배열을 가지고 으쌰으쌰 가공하려고 이런 저런 시도를 해보았지만, 안되어서 어떻게 정상적인 순서와 그렇지 않은 것을 구분하지싶었다.
Boolean 으로 true/false처리를 하니까 정렬/중복 다 필요없어졌었다.
배열을 생성하려고 하면 새로운 IntArray를 생성하려고 하는 고집좀 버렸으면 한다..ㅎ