C++에서 배열을 M번 이어붙인 후 K번째 최솟값 구하는 방법

문제 개요

배열 A와 두 개의 정수 K, M이 주어졌을 때, 배열 A를 자기 자신에게 M번 이어붙인 결과에서 K번째 최솟값을 찾는 것이 이 글의 목표입니다.

예를 들어 배열이 A = [3, 1, 2], K = 4, M = 3이라고 가정해 보겠습니다. 배열을 3번 이어붙이면 [3, 1, 2, 3, 1, 2, 3, 1, 2]가 되고, 이 배열에서 4번째로 작은 요소는 2입니다.

접근 방법

배열을 실제로 M번 복사해 붙이면 불필요한 메모리와 시간이 낭비됩니다. 하지만 각 요소가 정확히 M번씩 반복된다는 점을 활용하면 훨씬 간단하게 해결할 수 있습니다.

1. 배열 A를 오름차순으로 정렬합니다.
2. 정렬된 배열에서 인덱스 ((K - 1) / M) 위치에 있는 값을 반환합니다.

이 방법이 성립하는 이유는 다음과 같습니다. 배열을 M번 이어붙인 뒤 정렬하면, 정렬된 원본 배열의 각 요소가 M개씩 연속해서 배치됩니다. 따라서 K번째 최솟값은 정렬된 배열의 (K - 1) / M 번째 위치에 있는 요소와 일치합니다.

C++ 구현 예제

#include<iostream>
#include<algorithm>
using namespace std;
int findKSmallestNumber(int A[], int N, int M, int K) {
    sort(A, A + N);
    return (A[((K - 1) / M)]);
}
int main() {
    int A[] = { 3, 1, 2 };
    int M = 3, K = 4;
    int N = sizeof(A) / sizeof(A[0]);
    cout << M << "번 이어붙인 후 " << K << "번째로 작은 수는: " << findKSmallestNumber(A, N, M, K);
}

실행 결과

3번 이어붙인 후 4번째로 작은 수는: 2

마무리

이 접근법의 시간 복잡도는 정렬 단계가 지배하므로 O(N log N)이며, 배열을 실제로 확장하지 않고도 K번째 최솟값을 빠르게 구할 수 있는 효율적인 방법입니다. 반복되는 배열에서 순서 통계(order statistic)를 구할 때 유용하게 활용할 수 있는 패턴이니 꼭 기억해 두세요.