First Missing Positive

First Missing Positive

1. 문제 내용

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

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

O(N)을 목표로 한다.

 

2. 접근 방법

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;
    }java

 

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

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;
    }java