[LeetCode 리트코드] Kth Missing Positive Number

문제

리스트로 주어지는 arr를 제외하고 없는 k번째 숫자를 구하여라. (모든 수는 자연수)

예

input : arr = [1, 2, 5, 6, 7, 10, 20], k = 5

output : 11

• 1번째 missing number : 3
• 2번째 missing number : 4
• 3번째 missing number : 8
• 4번째 missing number : 9
• 5번째 missing number : 11

추가사항

• arr의 길이는 1000.
• arr의 요소는 1이상 1000이하,
• k는 1이상 1000이하.
• arr는 오름차순 정렬

나의 솔루션

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        arrIdx = 0
        arrLen = len(arr)
        for i in range(1, arrLen + k + 1):
            if arrIdx >= arrLen or i != arr[arrIdx]:
                k -= 1
            else:
                arrIdx += 1
            if k == 0:
                return i

 

깨달은 점

처음에 arrLen을 쓰지 않고 그냥 len(arr)로 썼는데, 포문을 돌 때마다 arrIdx >= len(arr) 를 비교하기 때문에 느렸다.

혹시나 해서 처음부터 길이를 변수에 넣어서 했더니 훨씬 빨라졌다.  (48 ms 에서 44ms가 됨)

 

결과

Submission Detail

84 / 84 test cases passed.	Status: Accepted
Runtime: 44 ms Memory Usage: 14.5 MB	Submitted: 0 minutes ago