[프로그래머스] 순위
문제
n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.
선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항
- 선수의 수는 1명 이상 100명 이하입니다.
- 경기 결과는 1개 이상 4,500개 이하입니다.
- results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
- 모든 경기 결과에는 모순이 없습니다.
입출력 예
| n | results | return |
|---|---|---|
| 5 | [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] | 2 |
풀이
문제에서 중요한 정보를 요약하면 아래와 같다.
- A선수가 B선수보다 실력이 좋다면 A선수는 B선수를 항상 이긴다.
- 정확하게 순위를 매길 수 있는 선수의 수를 return하라.
- 정확하게 순위를 매길 수 있는 조건은 무엇일까?
정확하게 순위를 매길 수 있는 조건이 무엇인지를 유추해내는 것이 문제의 핵심이다.
입출력 예를 가지고 유추해보자.
예시에서 출력이 2인 이유는 참가자가 5명인데 2번 선수가 [4,3,1] 선수에게 졌고 [5] 선수에게 이겼기 때문이다.
즉 n명의 참가자가 있을 때, n-1번의 경기기록이 있어 4등인지 알 수 있었다.
그렇다면 5번 참가자는 어떨까?
5번 참가자는 4등을 한 2번 참가자에게 진 기록만이 있다.
경기기록이 하나밖에 없지만 4등에게 졌기 때문에 자동으로 5등이라고 할 수 있다.
5번 참가자의 경기기록은 하나밖에 없지만, 2번 참가자와 나머지 참가자들간의 경기기록으로부터 유추하면
5번 참가자는 [4,3,2,1] 선수에게 질 것이고 아무에게도 이길 수 없다.
왜냐면 이 문제의 규칙상 a 선수에게 진 b 선수는 a선수를 이긴 c선수에게 이길 수 없기 때문이다.
그리고 또 a 선수에게 이긴 b선수는 a 선수에게 진 c 선수에게는 이긴다.
이 규칙을 가지고 참가자들의 경기기록을 종합했을 때, 어떤 참가자가 n-1번의 경기기록을 가지게 되면 그 참가자의 순위를 정확히 매길 수 있는 조건이 만족하는 것이다.
각 참가자끼리의 경기기록이 있는지 없는지에 대해 2차원 Matrix로 표현하는 방법도 있지만, 나는 dictionary를 활용하여 각 참가자별 승리 리스트와 패배 리스트를 생성하여 이를 채워가는 식으로 문제를 해결하였다.
이를 코드로 옮기면 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def solution(n, results):
"""
순위를 확실히 알려면 n-1의 경기를 치뤘거나
n-1의 경기를 치룬사람이 n-1등이거나 2등일때 이겼거나 졌거나
"""
dic = {}
answer = 0
ranking = [0] * n
for win, lose in results:
if win in dic:
dic[win][1].append(lose)
else:
dic[win] = [[], [lose]]
if lose in dic:
dic[lose][0].append(win)
else:
dic[lose] = [[win], []]
#i한테 진 놈들중 그놈들한테 또 진놈을 append
#i한테 이긴놈중 그놈들한테 또 이긴놈을 append
for i in dic:
for w in dic[i][1]:
for ww in dic[w][1]:
if not ww in dic[i][1]:
dic[i][1].append(ww)
for w in dic[i][0]:
for ww in dic[w][0]:
if not ww in dic[i][0]:
dic[i][0].append(ww)
lose_list, win_list = dic[i]
if len(lose_list) + len(win_list) == n-1:
answer += 1
return answer