Daily LeetCode Challenge - 1539. Kth Missing Positive Number

Problem From.

https://leetcode.com/problems/kth-missing-positive-number/

오늘 문제는 arr 에 숫자가 주어졌을때, 1부터 빠진 수를 세어서 k 번째의 빠진 수를 찾는 문제였다.

문제의 제한 사항에 array 와 k 의 크기는 각각 1000으로 고정되어 있으므로 1~2000까지의 수중에서 찾으면 되었고, 시간복잡도를 줄여 O(N) 의 시간안에 찾기 위해, arr 를 set 으로 바꾸어 set 에서 contains 함수를 돌리도록 만들었다. set 에서 contains 함수를 돌리는 시간 복잡도는 O(1) 이 된다.

class Solution {
    fun findKthPositive(arr: IntArray, k: Int): Int {
        val numSet = arr.toSet()
        var cnt = 0
        for(i in 1..2000) {
            if(!numSet.contains(i)) cnt += 1
            if(cnt == k) return i
        }
        return 0
    }
}