[Programmers 코딩테스트 고득점 Kit] 순위

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

BFS를 이용하는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. results 벡터를 순회하면서 각 선수를 이긴 선수들을 저장하는 벡터 winners와 각 선수한테 진 선수들을 저장하는 벡터 losers를 정의해줍니다.

2. 각 선수들에 대해 BFS를 진행해주면서 (그 선수를 이긴 선수들의 합) + (그 선수한테 진 선수들의 합) = n - 1이라면 순위가 정해진 것입니다.

3. 2번을 통해 구한 순위가 정해진 선수들의 수를 반환해줍니다.

	#include <iostream>
	#include <string>
	#include <vector>
	#include <algorithm>
	#include <queue>
	using namespace std;
	const int MAX = 100 + 10;
	vector<int> winners[MAX];
	vector<int> losers[MAX];
	int getWinnerCnt(int player)
	{
	queue<int> q;
	q.push(player);
	bool visited[MAX] = { false, };
	visited[player] = true;
	int cnt = 0;
	while (!q.empty())
	{
	int cur = q.front();
	q.pop();
	cnt++;
	for (int winner : winners[cur])
	{
	if (visited[winner])
	{
	continue;
	}
	visited[winner] = true;
	q.push(winner);
	}
	}
	return cnt - 1;
	}
	int getLoserCnt(int player)
	{
	queue<int> q;
	q.push(player);
	bool visited[MAX] = { false, };
	visited[player] = true;
	int cnt = 0;
	while (!q.empty())
	{
	int cur = q.front();
	q.pop();
	cnt++;
	for (int loser : losers[cur])
	{
	if (visited[loser])
	{
	continue;
	}
	visited[loser] = true;
	q.push(loser);
	}
	}
	return cnt - 1;
	}
	int solution(int n, vector<vector<int>> results) {
	int answer = 0;
	for (int i = 0; i < results.size(); i++)
	{
	int winner = results[i][0];
	int loser = results[i][1];
	winners[loser].push_back(winner);
	losers[winner].push_back(loser);
	}
	for (int player = 1; player <= n; player++)
	{
	int cnt = getWinnerCnt(player);
	cnt += getLoserCnt(player);
	if (cnt == n - 1)
	{
	answer++;
	}
	}
	return answer;
	}
	int main(void)
	{
	int n = 5;
	vector<vector<int>> results = {
	{4, 3},
	{4, 2},
	{3, 2},
	{1, 2},
	{2, 5}
	};
	cout << solution(n, results) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~