C++로 정렬된 배열에서 k번째 누락된 요소 찾는 방법

이 튜토리얼에서는 주어진 정렬된 배열에서 k번째 누락된 요소를 찾는 프로그램을 작성해 보겠습니다.

배열의 최솟값부터 최댓값 사이에서 빠져 있는 숫자들 중 k번째 숫자를 찾는 것이 목표입니다. 예를 들어 배열이 {1, 2, 3, 5, 10}이고 k가 3이라면, 누락된 숫자는 4, 6, 7, 8, 9이므로 세 번째로 누락된 숫자인 7을 반환해야 합니다.

문제 해결 접근 방식

문제를 해결하는 단계는 다음과 같습니다.

정렬된 배열을 초기화합니다.
두 변수 difference와 count를 선언하고, count는 k 값으로 초기화합니다.
배열을 처음부터 끝까지 순회합니다.
- 현재 요소와 다음 요소가 연속되지 않은 경우(즉, arr[i] + 1 != arr[i + 1]):
  - 두 숫자 사이에 누락된 개수(difference)를 계산합니다.
  - difference가 count보다 크거나 같다면, 현재 요소에 count를 더한 값이 곧 k번째 누락된 숫자이므로 이를 반환합니다.
  - 그렇지 않으면 count에서 difference를 빼고 다음 구간으로 넘어갑니다.
배열 전체를 순회한 후에도 찾지 못했다면 -1을 반환합니다.

C++ 코드 구현

위 알고리즘을 C++로 구현한 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

int findMissingNumber(int arr[], int k, int n) {
    int difference, count = k;
    for (int i = 0; i < n - 1; i++) {
        if ((arr[i] + 1) != arr[i + 1]) {
            difference = arr[i + 1] - arr[i] - 1;
            if (difference >= count) {
                return arr[i] + count;
            } else {
                count -= difference;
            }
        }
    }
    return -1;
}

int main() {
    int arr[] = { 1, 2, 3, 5, 10 }, n = 5;
    int k = 3;
    cout << findMissingNumber(arr, k, n) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

동작 원리 살펴보기

예제 입력 {1, 2, 3, 5, 10}에서 k = 3일 때의 진행 과정을 단계별로 확인해 보겠습니다.

i = 0, 1: 1→2, 2→3은 연속된 숫자이므로 아무 작업도 하지 않습니다.
i = 2: 3과 5가 연속되지 않으므로 누락된 개수는 1개(숫자 4)입니다. difference(1) < count(3)이므로 count는 3 - 1 = 2가 됩니다.
i = 3: 5와 10이 연속되지 않으므로 누락된 개수는 4개(6, 7, 8, 9)입니다. difference(4) >= count(2)이므로 arr[3] + count = 5 + 2 = 7을 반환합니다.

시간 복잡도 분석

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 추가로 사용하는 공간은 상수 수준이므로 공간 복잡도는 O(1)입니다. 배열이 이미 정렬되어 있다는 전제 조건 덕분에 이진 탐색(O(log n))으로 더 최적화할 수도 있지만, 위의 선형 탐색 방식이 직관적이고 구현하기 가장 간단합니다.

마무리

이 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요. 도움이 되었기를 바랍니다!