LeetCode [1539]: Kth Missing Positive Number

📌 LeetCode [1539]: Kth Missing Positive Number

🔗 문제 링크

---

문제 설명 📄

정렬된 정수 배열 arr와 정수 k가 주어질 때, 배열에서 누락된 k번째 양의 정수를 반환합니다.

• 배열 arr는 1부터 시작하여 양의 정수만 포함합니다.

---

문제 접근 방식 📋

1. 포인터와 카운터 사용:
   • num은 현재 숫자를, index는 배열의 위치를 추적합니다.
   • count는 누락된 숫자를 추적합니다.
2. 누락된 숫자 확인:
   • 현재 숫자 num이 배열 arr에 없는 경우:
     • count를 증가시키고, num도 증가시킵니다.
   • 현재 숫자 num이 배열 arr에 있는 경우:
     • 배열의 다음 위치로 이동하며 num을 증가시킵니다.
3. 반복 조건:
   • count가 k에 도달할 때까지 위 작업을 반복합니다.
4. 결과 반환:
   • 마지막으로 확인된 숫자에서 1을 뺀 값을 반환합니다.

---

Solution 💻

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        count = 0
        index = 0
        num = 1
        while count != k:
            if index >= len(arr):
                num += 1
                count += 1
            else:
                if arr[index] > num:
                    num += 1
                    count += 1
                elif arr[index] == num:
                    index += 1
                    num += 1
                else:
                    index += 1

        return num - 1

시간 복잡도 분석 ⏲️

• 최악의 경우:
  • 배열의 길이가 n이고 k가 매우 큰 경우, 모든 숫자를 확인해야 하므로 (O(k + n)).
• 최적의 경우:
  • 배열의 길이가 짧고 k가 작으면 (O(k)).

공간 복잡도 분석 🗄️

• 추가 공간 사용:
  • 변수 count, index, num만 사용.
• 총 공간 복잡도: (O(1)).

---

리팩토링 🛠️

개선된 코드

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        max_value = max(arr) + k
        bitmask = [False] * (max_value + 1)
        
        for num in arr:
            bitmask[num] = True
        
        missing_count = 0
        for i in range(1, len(bitmask)):
            if not bitmask[i]:
                missing_count += 1
                if missing_count == k:
                    return i

리팩토링 후 시간 복잡도 ⏲️

• 시간 복잡도:
  • 비트마스크 초기화와 탐색: O(max⁡(arr)+k)O(max(arr) + k).
• 공간 복잡도:
  • 비트마스크 크기: O(max⁡(arr)+k)O(max(arr) + k).