2021-01-07] Kth Missing Positive Number

오늘의 문제:

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

Kth Missing Positive Number - LeetCode

 

이번 문제도 이해는 쉬웠던 것 같다!

입력값으로 주는 arr에 값을 제외한 [1~1000] 이하의 List의 입력값 k번째의 값을 구하는 것이다!

 

예시를 보며 같이 이해해보자

 

< 문제 예시 1~2 >

 

입력값으로 [2,3,4,7,11] 이 주어졌으니 해당 내용을 제외한 [1~1000]의 값은 [1,5,6,8,9,10,12,13 ... 1000] 이 된다. 

저 List에서 k=5번째의 값을 9하면 구인것이다! 바로 문제 풀이로 들어가보자

 

class Solution(object):
    def findKthPositive(self, arr, k):
        """
        :type arr: List[int]
        :type k: int
        :rtype: int
        """
        ans=[] # arr을 제외한 [1~1000]까지 쌓을 list
        i=1 # 값의 맨 첫번째 값인 1을 담는 변수 i
        while len(ans) != k: # 1000번째까지 갈필요 없이 k번째의 값까지만 채워지만 바로 종료!
            if i not in arr:
                ans.append(i) # arr에 포함되어 있지않으면 ans에 추가
            i=i+1
        return ans[k-1] # List의 index는 0부터 시작하니 k번째의 index는 k-1

<문제풀이의 성능>