LeetCode 448. Find All Numbers Disappeared in an Array

문제

길이 $n$인 정수 배열 $\texttt{nums}$가 주어지며, 배열의 각 원소는 $1$ 이상 $n$ 이하이다. $(n \le 10^5)$

$1$ 이상 $n$ 이하의 정수 중, $\texttt{nums}$에 포함되어 있지 않은 수들을 리스트에 담아 반환해라.

 

추가 조건

1. 리턴할 리스트를 제외하고 추가 공간 사용 x

2. 시간복잡도 $O(n)$으로 해결

 

시도

추가 조건대로 풀어보기 위해 많은 생각을 해봤다.

 

1. 해시셋을 써봐야겠다 -> 추가 공간 사용함

2. 1부터 하나씩 배열에 있는지 볼까? -> $O(n^2)$임

3. 정렬하면 공간을 안 쓰고 할 수 있을 것 같다. -> $O(n\log{n})$임

4. 각 비트가 몇 번 나왔는지 볼까? -> $O(n\log{n})$이고 공간도 더 씀

 

한 시간 정도 고민해 봤는데, 도저히 풀 자신이 없었다. ChatGPT 선생님께 도움을 청했다.

 

풀이

 

출처: ChatGPT

 

???????????????????????????????????????????????

 

 

이걸 혼자 떠올려서 푼 사람들이 있다면 존경의 박수를 보낸다.

나는 100시간을 더 줬어도 떠올리지 못 했을 것이다.

 

코드

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        for(int i : nums) {
            int v = Math.abs(i);
            if(nums[v-1] > 0) nums[v-1] *= -1;
        }
        List<Integer> answer = new ArrayList<>();
        for(int i=0;i<n;i++) if(nums[i] > 0) {
            answer.add(i+1);
        }
        return answer;
    }
}