First Missing Positive

First Missing Positive

문제 내용

주어진 Integer Array에 1부터 N까지의 수가 있다.

이중에 1이상의 수중에 첫번째로 없는 수를 찾아라

O(N)을 목표로 한다.

 

접근 방법

O(N)이라는 부분이 이 문제의 핵심이다.

만약에 쉽게 정리 한다면 Sorting O(NlogN)으로 문제를 해결할 수 있다.

 

그러나  O(N)의 속도는 Sorting으로 해결되지 않는다.

이런경우 자료 구조를 통한 접근을 우선적으로 생각할 수 있다.

나는 Priority Queue를 통한 접근을 생각했다.

값을 Push할 경우 O(LogN)

Delete할 경우 O(1)과

자리를 찾는데 걸리는 시간 최대 (N)이 걸릴 수 있다.

그래서 최대 O(N)으로 Priority Queue를 생각했다.

    public int firstMissingPositive(int[] nums) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((x,y)-> x - y);

        for(int i = 0; i < nums.length; i++){
            if(0 < nums[i]){
                pq.offer(nums[i]);
            }
        }

        int last = 1;

        if(pq.size() < 1 || pq.peek() != last) return 1;

        for(int i = 0; 0 < pq.size(); i++){
            int temp = pq.poll();
            if(1 < temp - last){
                return last + 1;
            } else {
                last = temp;
            }
        }

        return last + 1;
    }

 

그러나 문제의 제출 의도는 이건 아닌것 같다.

Hash를 통한 문제 접근을 원한 것으로 보인다.

문제의 내용으로 보면 완전한 Array는 다음과 같은 모습이다.

[1,2,3...N]

여기서 한개가 빠지게 된다면 그것이 답이고, Array가 가득차있다면 N+1이 답이 된다.

만약

[3,1,2] 가 있다고 가정을 하면 Hash를 통해 다음과 같이 접근할 수있다.

1. Array의 길이는 3이다. 숫자가 가득 찾다고 가정하면 최대 숫자는 3이다. 그럼으로 4이상의 숫자는 무의미 하다

- 0이하 수는 모두 0으로 치환한다 (불필요)

- 4이상의 숫자는 무의미하다 (불필요)

- 4로 나머지 처리를 했을때 나올 수 있는 최대 수는 3이다.

- 나머지 처리는 그 값이 아무리 높아도 4미만으로 나온다. (1 +4 + 4) % 4 = 1 

2. Array의 시작은 Zero Base다

- 1일경우 [1] Array의 0에 1이 위치하게 된다.

- 1의 위치는 1-1인 0 Index이다

3. 5이상의 숫자는 4로 나누었을때 나머지 수가 있다.

= 6/5 = 1.xxxx

 

상기 내용을 바탕으로 문제를 풀면 다음과 같다.

- 0 Base에 3이 있다.

- 3 %4 = 3

- 3 - 1 => Index 2에 지정 숫자가 있다는 것을 알린다

- [3,1,2] + hash 4 = [3,1,6]

- 1Base에 1이 있다

- 1의 위치는 Index 0이다

- [3,1,6] + hash 4 = [7,1,6]

- 6의 위치는 6 % 4인 2이다

- [7,1,6] + hash 4 = [7,5,6]

 

[7,5,6] 을 모두 hash로 나누어서 0보다 크다면 상기 행위를 통해서 한번이라도 해당 Position에 숫자가 더해졌다는 의미가 된다.

이경우 답은 Hash 값인 4가 답이 된다.

해당 설명을 코드로 나타내면 아래와 같다.

    public int firstMissingPositive(int[] nums) {
        int hash = nums.length + 1;

        for (int i = 0; i < nums.length; i++) {
            if(nums[i] <= 0 || hash <= nums[i]) nums[i] = 0;
        }

        for (int i = 0; i < nums.length; i++) {
            int idx = nums[i] % hash;
            if(0 < idx) nums[idx - 1] += hash;
        }

        for (int i = 0; i < nums.length; i++) {
            if(nums[i] / hash == 0) return i+1;
        }

        return hash;
    }