[백준 2238번] - 경매 / C++ (stable_sort)

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, 정수)이 경매에 참여한(가격을 제시한) 순서대로 주어진다.

출력

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

----------------------------------------------------------------------------------------------------

풀이

<C++>

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

pair<int,int> arr[100001];

bool Acending(pair<string, int> a, pair<string, int> b) {
	return a.second < b.second;
}

bool Acending2(pair<int, int> a, pair<int, int> b) {
	if (a.second == b.second) {
		return a.first < b.first;
	}
	return a.second < b.second;
}

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

	int U;
	cin >> U;

	int N;
	cin >> N;

	string name;
	int money;

	vector<pair<string, int>> v;

	for (int i = 0; i < N; ++i) {
		cin >> name >> money;
		v.push_back({ name, money });
	}

	stable_sort(v.begin(), v.end(), Acending);

	string answerName;
	int answerMoney;
	bool truelyEnd = false;

	for (int i = 0; i < N - 2; ++i) {
		if (v[i].second == v[i + 1].second) {
			if (i == N - 3) {
				if (v[i + 1].second < v[i + 2].second) {
					answerName = v[i + 2].first;
					answerMoney = v[i + 2].second;
					truelyEnd = true;
					break;
				}
			}
			else {
				continue;
			}
		}
		else if (v[i].second < v[i + 1].second) {
			if (i == 0) {
				answerName = v[i].first;
				answerMoney = v[i].second;
				truelyEnd = true;
				break;
			}
			else if (v[i + 2].second > v[i + 1].second) {
				answerName = v[i + 1].first;
				answerMoney = v[i + 1].second;
				truelyEnd = true;
				break;
			}
			else {
				continue;
			}
		}
	}

	if (truelyEnd) {
		cout << answerName << ' ' << answerMoney;
	}
	else {
		for (int i = 0; i < N; ++i) {
			arr[v[i].second].first = v[i].second;
			arr[v[i].second].second += 1;
		}
		
		stable_sort(arr, arr + N, Acending2);

		int j;

		for (int i = N - 1; i >= 0; --i) {
			if (arr[i].first == 0) {
				j = i + 1;
				break;
			}
		}

		for (int i = 0; i < N; ++i) {
			if (arr[j].first == v[i].second) {
				cout << v[i].first << ' ' << v[i].second;
				break;
			}
		}
	}

	return 0;
}

solved.ac 기준으로 실버V 문제인데도 불구하고 조건들이 까다로워서 푸는데 꽤나 고생했다. 천천히 코드를 살펴보도록 하자.

 

1. U와 N을 입력받는다.

 

2. pair를 갖는 vector에 이름과 경매가를 넣는다.

 

3. vector에 대해 stable_sort를 진행한다.

 - stable_sort 란 sort는 같은 값을 가지는 값들에 대해 원래 입력받은 순서대로 정렬됨을 보장하지 못한다. 이를 보장해주는 것이 stable_sort라고 생각하면 된다.

 

4. 경매가들의 비교를 진행한다.

-> 값이 같으면, continue

-> 값이 다르면, 그 다음값과도 비교하여 같으면 continue, 다르면 answer에 입력

-> 예외처리, i == 0 인경우와 i == N-2 인경우는 처음과 끝이므로 다르게 처리해준다.

-> 반복문을 모두 돌기전에 올바르게 답을 입력하고 반복문을 탈출했을때는 truelyEnd 라는 boolean 값에 true를 넣어준다. 그렇지 못한 경우 false 그대로 유지.

 

5. boolean 이 true인 경우, 그냥 답을 출력한다.

 

6. boolean 이 false인 경우, 경매가와 중복횟수를 pair로 묶은뒤 이를 모두 arr 배열에 담는다. 그리고 arr에 대한 stable_sort를 진행한다.

 

7. arr배열을 전역으로 선언했으므로 pair 쌍이 {0, 0}으로 채워져 있다. 따라서 index를 N-1부터 빼가면서 {0,0} 인 index를 찾고, 찾은 경우 index에 1을 더해 최소횟수를 가지는 값을 가지는 index를 찾는다.

 

8. 마지막 반복문에서 arr배열의 최소횟수를 가지는 가격과 vector를 비교하여 가장 첫번째로 같은 값이 나오면 그 index의 이름과 가격을 출력한다.

 

----------------------------------------------------------------------------------------------------

푸는데 2시간정도 걸린 문제인데 분명히 간단하게 푸는 방법이 있을 것이라고 생각한다. 코드를 간략화하는 작업을 좀 해보아야겠다. 혹시나 좋은 답안이 있다면 댓글로 알려주시면 감사하겠습니다.