[Java] LeetCode 1539. Kth Missing Positive Number

[Java] LeetCode 1539. Kth Missing Positive Number

 

문   제 : 

일차원 배열 arr[] 이 주어진다.

정수 k가 주어진다.

arr은 양의 정수로만 이루어져 있고 , 정렬되어 있다.

arr에 포함되지 않는 정수 중 k번째의 정수를 구하여라.

 

Constraint

{ 1 <= arr.length <= 1000 }

{ 1 <= arr[i] <= 1000 }

{ 1 <= k <= 1000 }

{ arr[i] < arr[j+1] for 1 <= i <= j <= arr.length }

 

Example )

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: 
The missing positive integers are [1,5,6,8,9,10,12,13,...]. 
The 5th missing positive integer is 9.

//////////////////////////////////////////////////////////

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: 
The missing positive integers are [5,6,7,...]. 
The 2nd missing positive integer is 6.

 

---

접   근 : 

반복문을 이용한 검사

---

해   결 : 

숫자를 1부터 시작해서 셀 것이다. (cnt)

먼저 arr 배열 첫 번째 값부터 비교를 해서,

cnt 값이 arr[j] 보다 작다면 -> arr에 포함되어 있지 않다는 뜻이므로, k--를 해준다.

만약 cnt 값이 arr[j]와 같다면 다음 arr 값을 비교해야 하므로 j를 올려준다.

이 과정에서 arr의 최댓값(마지막 데이터)에 도달하게 되면, cnt는 더 이상 arr에 포함되어 있을 수가 없다.

   (무조건 더 크다.)

따라서 매 숫자가 올라갈 때마다 k를 빼준다.

이렇게 k가 0이 될 때까지 빼준다.

그리고 마지막에 cnt가 하나 더 더해지므로 return 값은 cnt-1로 반환해준다.

---

결   과  :

class Solution {
    public int findKthPositive(int[] arr, int k) {
        int cnt = 1;
        int j = 0;

        while(k > 0){
            if(j < arr.length){
                if(arr[j] > cnt) k--;
                else if(arr[j] == cnt) j++;
            }
            else {
                k--;
            }
            
            cnt++;
        }

        return cnt-1;
    }
}