(c++)프로그래머스 코딩테스트 연습 - 순위

programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

[풀이]

1. 각 선수들이 이긴 선수들의 번호와 진 선수들의 번호를 따로 저장하였다.

2. bfs를 이용하여 i번 선수보다 윗 순위인 선수들의 수(Up[i])와 아래 순위인 선수들의 수(Down[i])를 따로 세었다.

3. Up[i] 와 Down[i]를 합했을 때 n-1이 나오면 그 선수의 순위를 정확히 알 수 있으므로 cnt++

 

#include <string>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;
const int Max = 101;
vector<int>win[Max];
vector<int>lose[Max];
bool check[Max];
int cnt = 0;
int Up[Max];
int Down[Max];

void getInfo(vector<vector<int>>result) {
	for (int i = 0; i < result.size(); i++) {
		win[result[i][0]].push_back(result[i][1]);
		lose[result[i][1]].push_back(result[i][0]);
	}
}

void bfs(int N) {
	memset(check, false, sizeof(check));
	queue<int>q;
	check[N] = true;
	//순위 낮은 선수들 수 세기
	for (int i = 0; i < win[N].size(); i++) {
		q.push(win[N][i]);
		check[win[N][i]] = true;
		Down[N]++;
	}
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < win[x].size(); i++) {
			if (check[win[x][i]] == true)
				continue;
			check[win[x][i]] = true;
			Down[N]++;
			q.push(win[x][i]);
		}
	}
	//순위 높은 선수들 수 세기
	for (int i = 0; i < lose[N].size(); i++) {
		q.push(lose[N][i]);
		check[lose[N][i]] = true;
		Up[N]++;
	}
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < lose[x].size(); i++) {
			if (check[lose[x][i]] == true)
				continue;
			check[lose[x][i]] = true;
			Up[N]++;
			q.push(lose[x][i]);
		}
	}
}

//해당 선수 위 아래로 n-1명 있으면 그 선수의 순위는 정확하게 알 수 있음
int getResults(int n) {
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (Up[i] + Down[i] == n - 1)
			cnt++;
	}
	return cnt;
}

int solution(int n, vector<vector<int>> results) {
	int answer = 0;
	getInfo(results);
	for (int i = 1; i <= n; i++) {
		bfs(i);
	}
	answer = getResults(n);
	return answer;
}