C++로 정렬된 배열에서 K번째 누락된 요소 찾기

정렬된 서로 다른 숫자들의 배열 A가 주어졌을 때, 배열의 가장 왼쪽 숫자를 기준으로 K번째 누락된 숫자를 찾는 문제입니다. 예를 들어 배열이 [4, 7, 9, 10]이고 k = 1이라면, 답은 5가 됩니다.

접근 방법: 이진 탐색 활용

배열이 정렬되어 있으므로 선형 탐색(O(n)) 대신 이진 탐색(O(log n))을 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 두 인덱스 사이에 실제 존재하는 요소 수와 있어야 할 요소 수의 차이, 즉 '누락된 개수'를 계산하는 것입니다.

알고리즘 단계

• n := 배열의 크기로 설정하고, low := 0, high := n - 1로 초기화합니다.
• 만약 nums[n - 1] - nums[0] + 1 - n < k 라면, 누락된 숫자가 배열 범위 밖에 있다는 의미이므로 다음을 반환합니다.
  nums[n - 1] + (k - (nums[n - 1] - nums[0] + 1 - n))
• low < high - 1 동안 반복합니다.
  • mid := low + (high - low) / 2
  • present := mid - low + 1 (구간 내 실제 요소 개수)
  • absent := nums[mid] - nums[low] + 1 - present (구간 내 누락된 개수)
  • 만약 absent >= k 라면 high := mid, 그렇지 않으면 k에서 absent을 빼고 low := mid
• 최종적으로 nums[low] + k를 반환합니다.

다음 구현 예시를 통해 더 자세히 이해해 보겠습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int missingElement(vector<int>& nums, int k) {
        int n = nums.size();
        int low = 0;
        int high = n - 1;
        if(nums[n - 1] - nums[0] + 1 - n < k) return nums[n - 1] + (k
        - ( nums[n - 1] - nums[0] + 1 - n)) ;
        while(low < high - 1){
            int mid = low + (high - low) / 2;
            int present = mid - low + 1;
            int absent = nums[mid] - nums[low] + 1 - present;
            if(absent >= k){
                high = mid;
            }else{
                k -= absent;
                low = mid;
            }
        }
        return nums[low] + k;
    }
};
main(){
    vector<int> v = {4,7,9,10};
    Solution ob;
    cout << (ob.missingElement(v, 1));
}

입력

[4,7,9,10]
1

출력

5

복잡도 분석

• 시간 복잡도: O(log n) — 매 반복마다 탐색 범위가 절반으로 줄어듭니다.
• 공간 복잡도: O(1) — 추가 메모리 없이 상수 공간만 사용합니다.

이처럼 이진 탐색을 활용하면 대규모 정렬 배열에서도 빠르게 K번째 누락된 요소를 찾을 수 있습니다.