C++에서 가장 낮은 값을 가진 K 항목 찾기

이 문제에서는 항목과 해당 값과 정수 k로 구성된 목록이 제공됩니다. 우리의 임무는 가장 낮은 값을 가진 K개의 항목을 찾는 것입니다.

문제 설명: 목록에서 값이 가장 낮은 k 항목을 찾아야 합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력: 항목 값 ={ {항목1, 200}, {항목2, 100}, {항목3, 500}, {항목4, 400}} k =2

출력: 항목1, 항목2

설명:

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

솔루션 접근 방식

이 문제에 대한 해결책은 탐욕스럽게 가장 값이 작은 k개 항목을 찾는 것입니다. 먼저 항목 목록을 값의 오름차순으로 정렬합니다. 이 정렬된 목록에서 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;
   int n = 3;
   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(n, 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