백준 5766번 할아버지는 유명해! // C++

문제

 

"그 뉴스" 를 보고 온 가족이 들떴습니다. 모두들 할아버지께서 수 십년간 굉장히 실력있는  브릿지(카드게임의 일종) 선수였다는 것은 알고 있었지만, 할아버지가 역대 최고의 bridge 선수로서 기네스북에 오른다는 소식은 정말이지 놀라웠죠!

IBA(국제 브릿지 협회)는 수 년간, 매주 가장 실력있는 선수들의 랭킹 정보를 기록해왔습니다.  매주 랭킹에 선수의 이름이 오를 때마다 선수의 포인트가 1포인트씩 오르는데, 할아버지께서 가장 많은 포인트를 얻어서 최고의 브릿지 선수로 선정되었습니다.

할아버지께는 그와 브릿지 순위를 경쟁하는 친구들이 많이 있었기 때문에, 할아버지는 어떤 선수(들)가 2등을 했는지 정말 궁금하셨습니다.  

IBA 랭킹 정보는 이제 온라인에 올라와 있고, 할아버지께서 당신에게 도움을 요청했습니다. 당신은 매주마다의 랭킹 정보 리스트를 인풋으로 받아 2등 선수가 누구인지 알아내는 프로그램을 짜야 합니다.

입력

각 선수는 1~10000까지의 정수(선수 번호)로 식별됩니다. 인풋은 여러 테스트 케이스들로 구성됩니다.

테스트 케이스의 첫 행에는 두 정수 N과 M이 주어지는데, 다음 행부터 N(2<=N<=500)주 동안의 매주 상위 M(2<=M<=500)명의 랭킹 정보가 주어짐을 의미합니다.

그 다음 N행의 인풋이 주어지는데 각 행은 한 주의 랭킹 정보입니다. 각 행은 공백으로 구분되는 M개의 정수들이 주어집니다.  

• 각 테스트 케이스에는 최고점의 선수가 단 한 명만 존재합니다.
• 매주마다의 랭킹 정보에는 서로 다른 M개의 선수 번호가 주어집니다.

N과 M이 모두 0으로 주어지는 행이 인풋의 마지막입니다.

출력

각 테스트 케이스마다,  당신의 프로그램은 한 행에 2등인 선수(들)의 번호를 출력해야 합니다. 2등인 선수가 두 명 이상인 경우(동점자 발생), 각 선수 번호를 공백으로 구분하여 오름차순으로 출력해야 합니다.

 

---

 

풀이

 

N * M만큼 입력을 받고, 빈도의 순위가 2위인 것을 모두 출력하는 문제이다.

 

x번의 선수를 입력 받으면, 점수를 1점씩 더해주면서 모든 선수의 점수를 계산한 뒤 점수에 대해 내림차순으로 정렬했다.

 

또한 출력은 동점자인 경우 오름차순으로 해야하므로 선수의 번호에 대해선 오름차순으로 정렬했다.

 

그리고, 공동 1위가 있을 경우를 생각하여 앞 사람과 점수를 비교하여 다를 경우에만 2위가 될 수 있기 때문에 rank라는 변수를 사용하여 현재 몇 등인지를 확인하였다.

 

 

 

---

 

코드

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

using namespace std;

typedef struct _info {
	int num;
	int score;
}info;

bool compare(info a, info b);

int main() {
	int n, m;

	while (true) {
		cin >> n >> m;

		if (n == 0 && m == 0)
			break;

		info player[10001];
		for (int i = 0; i <= 10000; i++) {
			player[i].num = i;
			player[i].score = 0;
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				info temp;
				cin >> temp.num;

				player[temp.num].score++;
			}
		}

		sort(player, player + 10001, compare);

		int rank = 1;

		for (int i = 1; i < 10001; i++) {
			if (player[i].score != player[i - 1].score && rank == 1) { // 앞 사람이 1위이고 내가 2위일 경우
				rank = 2;
				printf("%d ", player[i].num);
			}
			else if (player[i].score == player[i - 1].score && rank == 2) // 앞 사람이 2위이고 나도 2위일 경우
				printf("%d ", player[i].num);
			else // 3위부터는 필요없으므로 break
				break;
		}

		printf("\n");
	}
}

bool compare(info a, info b) {
	if (a.score == b.score)
		return a.num < b.num;
	else
		return a.score > b.score;
}