C++로 정렬된 두 배열의 K번째 요소 찾기

이 튜토리얼에서는 정렬된 두 배열을 하나로 병합한 뒤, 그 결과에서 K번째 요소를 찾는 프로그램을 C++로 작성해 보겠습니다.

이 문제는 병합 정렬(Merge Sort)의 핵심 아이디어인 '두 포인터를 이용한 병합' 기법을 활용하면 간단하게 해결할 수 있습니다.

문제 해결 접근 방식

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

• 정렬된 두 개의 배열을 초기화합니다.
• 두 배열의 길이의 합(m + n)만큼의 크기를 가진 새로운 배열을 준비합니다.
• 두 배열을 순회하면서 작은 값부터 차례대로 새 배열에 병합합니다.
• 병합이 완료된 배열에서 k번째 요소(인덱스 k-1)를 반환합니다.

C++ 구현 코드

위의 로직을 실제 코드로 구현하면 다음과 같습니다.

#include <iostream>
using namespace std;

int findKthElement(int arr_one[], int arr_two[], int m, int n, int k) {
    // 두 배열을 병합한 결과를 저장할 배열
    int sorted_arr[m + n];
    int i = 0, j = 0, index = 0;

    // 두 배열을 모두 순회하며 작은 값부터 병합
    while (i < m && j < n) {
        if (arr_one[i] < arr_two[j]) {
            sorted_arr[index++] = arr_one[i++];
        } else {
            sorted_arr[index++] = arr_two[j++];
        }
    }

    // 첫 번째 배열에 남은 요소 처리
    while (i < m) {
        sorted_arr[index++] = arr_one[i++];
    }

    // 두 번째 배열에 남은 요소 처리
    while (j < n) {
        sorted_arr[index++] = arr_two[j++];
    }

    // k번째 요소 반환 (인덱스는 k-1)
    return sorted_arr[k - 1];
}

int main() {
    int arr_one[5] = {1, 3, 5, 7, 9};
    int arr_two[5] = {2, 4, 6, 8, 10};
    int k = 7;

    cout << findKthElement(arr_one, arr_two, 5, 5, k) << endl;

    return 0;
}

실행 결과

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

7

예제에서 두 배열 {1, 3, 5, 7, 9}와 {2, 4, 6, 8, 10}을 병합하면 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}이 되고, 이 중 7번째 요소는 7입니다.

시간 및 공간 복잡도

• 시간 복잡도: O(m + n) — 두 배열의 모든 요소를 한 번씩 순회합니다.
• 공간 복잡도: O(m + n) — 병합된 결과를 저장하기 위한 추가 배열이 필요합니다.

참고로, 추가 배열 없이 두 포인터만으로 K번째 요소까지만 순회하면 공간 복잡도를 O(1)로 최적화할 수 있으며, 더 나아가 이분 탐색(Binary Search)을 활용하면 시간 복잡도를 O(log(min(m, n)))까지 줄일 수 있습니다.

마무리

지금까지 C++에서 정렬된 두 배열을 병합하여 K번째 요소를 찾는 방법을 알아보았습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.