문제:
n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정화하게 순위를 매길 수 없습니다.
선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.
풀이 방법:
각 선수가 이긴 선수와 진 선수의 정보를 hash방식으로 정리하고 한 선수의 win정보의 길이와 lose정보 길이를 합쳤을 때 n-1과 같아지면 그 선수의 순위를 알 수 있게 된다. 또한 실력의 차이가 극명해서 실력이 낮은 사람이 높은 사람을 이길 수 없다고 한다. 따라서 정보를 가지고 있지 않지만 이 조건을 통해서 정보를 다시 얻을 수 있게 된다.
입출력 예시를 통해서 살펴 보면 2번선수의 경우에는 모든 경기기록이 있어서 순위를 알 수 있지만 5번 선수는 2번 선수와의 기록이 있지만 순위를 유추할 수 있다. 왜냐하면 2번이 1,3,4번 선수한테 졌는데 5번이 2번한테 졌으므로 5번은 당연히 1,3,4번 선수한테 진다는 것을 알 수 있다.(1,3,4 > 2 > 5) 또한 2번이 5번을 이겼기 때문에 5번이 이긴 사람도 당연히 이길 수 있다. (이 문제에서는 이러한 케이스가 없긴 하다.)
처음에는 리스트로 했더니 시간초과가 발생해서 이를 set으로 바꿔서 했더니 시간초과가 발생하지 않았다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | def solution(n, results): answer=0 win={} lose={} for i in range(1,n+1): win[i]=set() lose[i]=set() results.sort() for i in range(1,n+1): for re in results: if re[0]==i: win[i].add(re[1]) if re[1]==i: lose[i].add(re[0]) for j in win[i]: lose[j].update(lose[i]) for j in lose[i]: win[j].update(win[i]) for i in range(1,n+1): if len(win[i])+len(lose[i])==n-1: answer+=1 return answer | cs |
문제 링크:
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]1009. 분산처리 (0) | 2019.08.01 |
|---|---|
| [Programmers]Lv 3.배달 (3) | 2019.07.31 |
| [Programmers]Lv3. 가장 먼 노드 (0) | 2019.07.29 |
| [Programmers]Lv 4. 3xn 타일링 (2) | 2019.07.28 |
| [BOJ]2805. 나무 자르기 (0) | 2019.07.27 |