[백준 8978] 올림픽 (C++)

문제 링크: https://www.acmicpc.net/problem/8979

8979번: 올림픽

1. 주의할 점

- 전체 메달 수의 총합이 100만이다. -> 금 X M+ 은 X M + 동 X M (M은 특정 수)로 하기엔 M을 쉽게 생각하지 못했다

- 찾고자 하는 index에 집중하지 말고 해당 index의 금은동 갯수에 집중한다.

 

2. 구현

- 첫 번째 방식:  금은동을 전부 String으로 바꾼후, Map을 이용해서 구현하려고 했다. (실패)

  =>금 2 은 22 동 2 와 금22 은 2 동 2 와 같은 케이스에 대한 예외처리가 까다롭다

- 두 번째 방식: 우선순위큐를 사용한다 (성공)

  => 찾고자 하는 금은동 각각의 갯수와 같다면 while문에서 빠져 나오고, 그렇지 않다면 cnt를 1씩 더하면서 찾는다

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <map>
#include <string>
using namespace std;

struct info {
	int gold, silver, bronze;
};
info tmp;
struct cmp{
	bool operator()(info &a, info &b) {
		if (a.gold == b.gold) {
			if (a.silver == b.silver) 
				return a.bronze < b.bronze;			
			return a.silver < b.silver;
		}
		return a.gold < b.gold;
	}
};
int main() {
	int country, idx, g, s, b, tidx, tg, ts, tb;
	cin >> country >> tidx;
	priority_queue<info, vector<info>, cmp> pq;
	for (int i = 0; i < country; i++) {
		cin >> idx >> g >> s >> b;
		if (idx == tidx) { tg = g; ts = s; tb = b; }
		tmp.bronze = b;
		tmp.silver = s;
		tmp.gold = g;
		pq.push(tmp);
	}
	int cnt = 1;
	while (!pq.empty()) {
		int cg = pq.top().gold;
		int cs = pq.top().silver;
		int cb = pq.top().bronze;
		pq.pop();
		if (tg == cg && ts == cs && tb == cb) 	break;	
		else	cnt++;
	}
	cout << cnt;
	system("pause");
	return 0;
}