프로그래머스 순위

- 문제 설명

 

n명의 권투선수의 1:1 경기 기록을 가지고 있을 때, 주어진 경기기록을 가지고 정확한 순위를 매길 수 있는 권투선수의 수를 return 하는 solution 함수 작성

 

 

- 입력

 

1) 선수의 수 : 1 <= n <= 100

2) 경기결과 : 1 <= [벡터] <= 4500

3) [A, B] : A 선수가 B 선수를 이겼다는 의미

 

 

- 출력

 

주어진 경기 결과를 통해 정확하게 순위를 매길 수 있는 선수의 수

 

 

* 문제 풀이의 핵심

 

플로이드워셜 알고리즘을 선뜻 이해하기 어려워 그 알고리즘을 사용하지 않고 풀 수 있는 방법을 사용하여 문제를 해결하였습니다.

 

SET 자료구조와 반복문을 사용하여 권투선수의 강함, 약함 순서를 정의하는 방식으로 풀었습니다. (이해하는데 참고한 사이트는 하단에 링크 표시하였습니다.)

 

 

0. 알고리즘

 

1) 주어진 벡터를 순회하면서 자신보다 강한 선수, 약한 선수를 찾는다.

 

2) 1번 선수부터 n번 선수까지 순회하면서, 자신보다 강한 선수의 SET 리스트를 가져온다.

 

ex) SET 리스트를 가져온다는 것이란?

 

2번 선수보다 강한 선수 : 1, 3, 4

5번 선수보다 강한 선수 : 2

 

위와 같은 선수 벡터가 있을 때

 

5번 선수보다 2번 선수가 강하다면, 2번 선수보다 강한 선수들은 모두 5번 선수보다 강한 것이 된다.

 

2번 선수보다 강한 선수 : 1, 3, 4

5번 선수보다 강한 선수 : 2, 1, 3, 4

 

결과적으로 5번 선수보다 강한 선수들은 1, 2, 3, 4 번 선수가 된다.

 

3) 1번 선수부터 n번 선수까지 순회하면서, 자신보다 약한 선수의 SET 리스트를 가져온다.

 

4) 1) ~ 3) 을 n 번 반복한다.

 

=> 1번부터 n번 순서로 가져오기 때문에, n번 선수의 수정된 순서가 1번 선수의 순서와 다를 수 있는 경우가 발생할 수 있으므로 n번 순회해준다.

 

 

1. SET 자료구조

 

1) 사용이유 : SET은 원소들의 값이 중복으로 저장되지 않기 때문에 순서를 유지하기 위해 사용

 

2) 사용방법 :

 

- SET 자료구조의 순회는 iterator

- 원소의 값은 *iterator

- 전체 SET의 삽입은 .begin() ~ .end() 까지

 

for (auto it = strong[i].begin(); it != strong[i].end(); it++) {
	strong[i].insert(strong[*it].begin(), strong[*it].end());
}

 

 

2. 정확한 순위를 나타내려면 순서가 N-1 개 필요

 

정확한 순위를 나타내기 위해서는 (자신보다 강한사람 + 자신보다 약한사람) 의 수가 N-1명이여야 합니다.

 

그 이하의 순서를 알고 있다면 정확한 순서를 찾을 수 없습니다.

 

 

3. 그림 설명

 

n = 5

results = [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]

 

예제 1) 입력이 위와 같을 때 자신보다 강한 선수, 약한 선수를 찾았을 때 결과

 

 

 

예제 2) 입력이 위와 같을 때 자신보다 강한 선수, 약한 선수의 SET 리스트를 가져온 결과

 

 

 

- 소스코드

 

#include <string>
#include <vector>
#include <set>

using namespace std;

vector<set<int>> strong(101);
vector<set<int>> weak(101);

int solution(int n, vector<vector<int>> results) {
	int answer = 0;
	
	int i, depth;
	// 나를 기준으로 순서를 정함
	for (i = 0; i < results.size(); i++) {
		// 나보다 약한 선수
		weak[results[i][0]].insert(results[i][1]);
		// 나보다 강한 선수
		strong[results[i][1]].insert(results[i][0]);
	}

	// 반영 안될 경우를 위해 n번 반복
	for (depth = 0; depth < n; depth++) {
		// 나보다 강한 선수들
		for (i = 1; i <= n; i++) {
			for (auto it = strong[i].begin(); it != strong[i].end(); it++) {
				strong[i].insert(strong[*it].begin(), strong[*it].end());
			}
		}

		// 나보다 약한 선수들
		for (i = 1; i <= n; i++) {
			for (auto it = weak[i].begin(); it != weak[i].end(); it++) {
				weak[i].insert(weak[*it].begin(), weak[*it].end());
			}
		}
	}

	// n-1 번 결과 존재시 정답
	for (i = 1; i <= n; i++) {
		int length = weak[i].size() + strong[i].size();
		if (length == (n - 1)) answer++;
	}

	return answer;
}

 

 

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

코딩테스트 연습 - 순위

 

 

- 제출한 코드

 

 

>  백준 아이디 : canoe726

>  사용언어 : C++

>  에디터 : Visual Studio 2017

>  궁금한점은 댓글로 남겨주세요

 

 

- 참고 : https://velog.io/@ajufresh/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%88%9C%EC%9C%84-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-Java