[C++] 백준 8979 올림픽 - 정렬, 구현 (sort, Implement)

문제 링크: 백준 8979번 - 올림픽

---

🔍 문제 요약

• 목표: 주어진 국가들의 금, 은, 동 메달 정보를 기반으로 등수를 구하기
• 규칙:
  1. 금메달 수가 많을수록 우선
  2. 금이 같다면 은메달 수로 비교
  3. 금, 은이 같다면 동메달 수로 비교
  4. 모두 같다면 공동 순위
• 입력:
  • 국가 수 N, 등수를 알고 싶은 국가 번호 K
  • 각 국가: 국가번호 금 은 동

---

💡 문제 분석

• 국가의 수는 최대 1,000
• 메달 수 총합은 1,000,000
• 등수를 정하기 위해 모든 국가 정보를 정렬한 뒤 K번 국가의 순위만 찾으면 됨

---

🧩 풀이 전략

1. 입력값 저장: vector<vector>로 국가별 정보를 저장 ([id, gold, silver, bronze])
2. 정렬: compare 함수를 사용하여 금-은-동 순으로 정렬
3. 등수 계산:
   • 이전 국가와 메달 수가 같다면 같은 순위
   • 다르면 현재 인덱스 + 1이 순위
4. K번 국가를 만나면 순위 출력

---

✅ 예제 입력 & 출력

입력
4 2
1 1 2 0
2 0 1 0
3 0 1 0
4 0 0 1

출력
2

 

---

🖥️ 코드 (C++)

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

using namespace std;

bool compare(const vector<int>& a, const vector<int>& b) {
	if (a[1] != b[1]) return a[1] > b[1];
	if (a[2] != b[2]) return a[2] > b[2];
	return a[3] > b[3];
}

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

	int n, k;
	cin >> n >> k;

	vector<vector<int>> country(n);

	for (int i = 0; i < n; i++) {
		int id, g, s, b;
		cin >> id >> g >> s >> b;
		country[i] = {id, g, s, b};
	}

	sort(country.begin(), country.end(), compare);

	int rank = 1;
	for (int i = 0; i < n; i++) {
		if (i > 0 && (
			country[i][1] != country[i - 1][1] ||
			country[i][2] != country[i - 1][2] ||
			country[i][3] != country[i - 1][3])) {
			rank = i + 1;
		}
		if (country[i][0] == k) {
			cout << rank << "\n";
			break;
		}
	}
	return 0;
}

---

⏱️ 시간복잡도 분석

국가 정보 입력	O(N)
정렬	O(N log N)
등수 계산	O(N)
👉 전체	O(N log N)

• N ≤ 1,000이므로 N log N도 가능

---

✨ 결론

• 정렬 + 순위 계산을 조합하여 간단하게 해결 가능
• O(N log N) 알고리즘으로 빠르고 정확하게 구현 가능
• 공동 순위 처리 조건을 잘 확인하자.