[Baekjoon/C++] 2238번 - 경매

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

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

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

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

 

입력

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

 

출력

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

 

---

풀이

#include <iostream>
using namespace std;

#define MAX 10001

int price[MAX];     // 각 가격으로 입찰한 사람의 수
string name[MAX];   // 가장 먼저 해당 가격으로 제시한 사람

int findResult();

int findResult() {
    int cnt = 100001;
    int result = 0;

    for (int i = 1; i < MAX; i++) {
        // 해당 가격을 제시한 사람이 없을때
        if (price[i] == 0) continue;

        // 더 적은 수의 사람이 입찰한 가격일때
        if (price[i] < cnt) {
            cnt = price[i];
            result = i;
        }
    }

    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int U, N;
    cin >> U >> N;

    while (N--) {
        string s;
        int p;
        cin >> s >> p;

        // 해당 가격으로 가장 먼저 제시한 사람의 이름 저장
        if (price[p] == 0) name[p] = s;

        price[p]++;
    }

    // 출력
    int result = findResult();
    cout << name[result] << ' ' << result << '\n';

    return 0;
}

 

    while (N--) {
        string s;
        int p;
        cin >> s >> p;

        // 해당 가격으로 가장 먼저 제시한 사람의 이름 저장
        if (price[p] == 0) name[p] = s;

        price[p]++;
    }

 사람의 이름과 그 사람이 제시한 가격을 입력 받는 부분의 코드이다. 아무도 제시하지 않은 가격으로 입찰한다면 name[]에 그 사람의 이름을 기록한다.

 

int findResult() {
    int cnt = 100001;
    int result = 0;

    for (int i = 1; i < MAX; i++) {
        // 해당 가격을 제시한 사람이 없을때
        if (price[i] == 0) continue;

        // 더 적은 수의 사람이 입찰한 가격일때
        if (price[i] < cnt) {
            cnt = price[i];
            result = i;
        }
    }

    return result;
}

 1. 가장 적은 수의 사람이 입찰한 가격
 2. 같다면 더 낮은 금액

 낙찰된 가격을 찾는 함수로 위와 같은 조건으로 답을 찾고, return한다.