C++로 값이 가장 작은 K개 항목 찾기

이 문제에서는 항목(item)과 해당 값(value)으로 구성된 리스트와 하나의 정수 k가 주어집니다. 우리의 목표는 값이 가장 작은 K개의 항목을 찾는 것입니다.

문제 설명

주어진 리스트 전체에서 값이 가장 작은 순서대로 k개의 항목을 골라내야 합니다.

예시를 통해 문제를 이해해 보겠습니다

입력: item-value = { {item1, 200}, {item2, 100}, {item3, 500}, {item4, 400} }, k = 2

출력: item1, item2

설명:

값이 가장 작은 두 요소는 값이 200인 item1과 값이 100인 item2입니다.

해결 접근 방법

이 문제는 탐욕적(greedy) 방식으로 손쉽게 해결할 수 있습니다. 먼저 항목 리스트를 값 기준으로 오름차순 정렬합니다. 그다음 정렬된 리스트의 앞부분에서 값이 가장 작은 k개의 항목을 차례로 선택하면 됩니다.

정렬에 소요되는 시간 복잡도는 O(n log n)이며, 이후 앞에서 k개만 출력하므로 전체적으로 효율적인 방법입니다.

솔루션 동작 예제 프로그램

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

bool compVal(pair<string, int> A, pair<string, int> B) {

    if (A.second == B.second)
        return A.first < B.first;
    return A.second < B.second;
}

int main() {

    int k = 2;
    vector<pair<string, int> > items;
    items.push_back(make_pair("item1", 350));
    items.push_back(make_pair("item2", 150));
    items.push_back(make_pair("item3", 500));
    items.push_back(make_pair("item4", 100));

    // 값 기준 오름차순 정렬
    sort(items.begin(), items.end(), compVal);

    cout<<k<<" items with least value are \n";
    for (int i = 0; i < min((int)items.size(), k); ++i)
        cout<<"Item : "<<items[i].first<<", value : "<<items[i].second<<endl;
    return 0;
}

출력 결과

2 items with least value are
Item : item4, value : 100
Item : item2, value : 150

위 예제에서 비교 함수 compVal은 두 항목의 값이 같을 경우 항목 이름을 기준으로 정렬하여 결과의 일관성을 보장합니다. 정렬이 완료된 후에는 리스트의 처음부터 최대 k개까지 출력하면 되므로, 항목 수가 k보다 적은 경우에도 min(items.size(), k)를 사용해 안전하게 처리할 수 있습니다.