[C++] 백준 2238번:경매 (pair)

문제링크

https://www.acmicpc.net/problem/2238

2238번: 경매

문제

경매는 여러 사람이 하나의 물건을 사려고 할 때, 각 사람이 원하는 가격을 제시하면 그 중 가장 높은 가격으로 물건을 팔게 되는 방식이다. 이러한 고전적인 경매 방식은 꽤 널리 쓰이는데, 최근에는 인터넷 쇼핑몰에서 반대의 경매 방식을 택하기도 한다. 즉, 여러 사람이 가격을 제시하면, 그 중 가장 낮은 가격으로 물건을 팔게 되는 방식도 쓰인다.

하지만 이럴 경우, 모든 사람들이 1원에 물건을 사겠다고 하는 사태가 발생할 수 있다. 따라서 같은 가격을 제시한 사람이 둘 이상일 경우에는 무효로 하는 방식이 쓰인다. 하지만 모든 가격을 여러 사람이 제시하는 경우도 있을 수 있기 때문에, 다음과 같은 방식으로 경매 당첨자를 선택하기로 한다.

우선 가장 적은 수의 사람이 제시한 가격을 찾는다. 이러한 경우가 여럿 있다면, 가장 낮은 가격으로 물건을 팔게 된다. 이때, 그 가격을 제시한 사람들 중에서 가장 먼저 제시한 사람이 물건을 살 수 있게 된다.

각각의 사람들이 제시한 가격이 주어졌을 때, 경매에 낙찰(당첨)되는 사람을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 U(1≤U≤10,000), N(1≤N≤100,000)이 주어진다. U는 금액의 상한이고, N은 경매에 참여한 회수이다. 다음 N개의 줄에는 사람 이름 S(공백 없는 알파벳 대소문자 10자 이하)와, 그 사람이 제시한 가격 P(1≤P≤U, 정수)이 경매에 참여한(가격을 제시한) 순서대로 주어진다.

출력

첫째 줄에 낙찰된 사람의 이름과 그 가격을 출력한다.

 

풀이

문제에 주어진 내용을 정리하면 아래와 같다.

1. 가장 적은 수의 사람이 제시한 가격을 찾는다.
2. 여러 경우라면 낮은 가격으로 판매한다.
3. 여러명이 위의 가격을 제시하였다면 가장 먼저 제시한 사람이 물건을 산다.

 

가격을 제시한 사람의 이름과 가격을 pair로 묶어 벡터에 저장하였다. 이렇게 하면 어떠한 가격을 가장 먼저 제시한 사람의 이름을 찾을 수 있다.

금액의 상한선이 10000원이기 때문에 크기가 10001인 int형 배열을 만들어주었다. 이 배열의 index는 가격으로 볼 수 있고 해당 index의 값은 그 가격이 나온 횟수로 볼 수 있다.

입력을 받으며 벡터에 이름과 가격을 저장하고, 배열에는 나온 횟수를 ++시켜준다.

1. 입력이 끝나고 나면 배열을 돌면서 가장 적게 나온 가격을 찾는다. (이 때 가장 적은 것은 한번도 나오지 않았을 경우도 있기 때문에 0을 제외하고 찾아야 한다.)
2. 벡터에서 위에서 찾은 가격을 가장 먼저 제시한 사람을 찾는다.

코드

#include <iostream>
#include <vector>
using namespace std;
 
int u, n, p;
string s;
int arr[10001];
vector<pair<string, int>> v;
 
int main() {
    cin >> u >> n;
    arr[0] = 100000;    // 최대로 나올 수 있는 횟수
 
    // 입력
    for (int i = 0; i < n; i++) {
        cin >> s >> p;
        arr[p]++;        // 가격이 나온 횟수 증가
        pair<string, int> tmp;
        tmp.first = s;
        tmp.second = p;
        v.push_back(tmp);
    }
 
    // 최소 횟수 탐색(인덱스는 가격)
    int count = 0;
    for (int i = 0; i < 10001; i++) {
        // 나온 횟수가 같을 경우까지 처리
        if (arr[i] > 0 && arr[i] < arr[count]) {
            count = i;
        }
    }
 
    // 가격을 가장 먼저 말한 사람 탐색
    for (int i = 0; i < n; i++) {
        if (v[i].second == count) {
            cout << v[i].first<<' ';
            break;
        }
    }
    cout << count;    //가격
 
}

 

메모

pair를 이용하여 풀어보았다. 알아두면 앞으로도 용이하게 사용할 수 있을 것 같다.