코딩테스트 연습 > 고득점 kit > 그래프 > 순위 Level 3문제입니다.
📖Problems
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 |
입출력 예 설명
2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.
🔍Institution
그래프 문제는 맨 처음에 그래프의 연결관계를 테이블이든 그래프든 설정해주어야 한다. 그래서 바로 그래프를 만들어주었다.
그래프 player
| player | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 0(짐) | 1,3,4 | 4 | 2 | ||
| 1(이김) | 2 | 5 | 2 | 3, 2 |
이제 2번째로, 정확하게 순위를 매길 수 있는 조건이 무엇인지 생각해보자.
정확하게 순위를 매길 수 있는 선수는 n-1 경기를 했을 경우에 알 수 있다. 이렇게 확실한 선수를 토대로 확인할 수 있는 선수도 찾아야 한다.
이것을 찾았다면 문제의 반은 접근한 것이다.
여기서 다시 주목해야 할 것은 “어떤선수 i를 이긴 j선수가 있을 때, j 선수를 이긴 사람들은 i 선수를 무조건 이긴다.”는 점이다.
예시케이스에서 2번 선수는 n-1경기를 했기 때문에 확실하게 순위를 알 수 있다. 이에 따라 5번 선수도 2번 선수에게 졌기 때문에 순위를 알 수 있다.
하지만 이렇게 순위가 몇인지까지 구한다면 아마도 산으로 갈 확률이 높다. 우리가 구해야 할 것은 ‘몇 명’인지 찾는 것이다.
그렇기 위해서는 위에서 제시한 ‘명제’에 주목해야 한다.
따라서 테이블을 수정하면 아래와 같다.
하지만 위 명제를 수행하기 위해서 좀 많이 애먹었다..
| player | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 0(짐) | 1,3,4 | 4 | 1,2,3,4 | ||
| 1(이김) | 2,5 | 5 | 2,5 | 3,2,5 |
여기서 경기기록을 확인한다.
| 경기기록 | 2 | 4 | 3 | 3 | 4 | | — | — | — | — | — | — |
경기기록이 n-1, 즉 4인 값은 총 2개 있으므로 return값이 2가 된다.
이를 토대로 접근해보았다.
🔍Approach
문제 풀이 과정에서 코드가 복잡해져서 player테이블을 2개로 나누었다.
| player | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 0(짐) | 1,3,4 | 4 | 2 | ||
| 1(이김) | 2 | 5 | 2 | 3, 2 |
여기서 win 리스트와 lose 리스트로 나누었다.
| win (index) | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 2 | 5 | 2 | 3, 2 |
| lose (index) | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1,3,4 | 4 | 2 |
Flow
각 선수마다 이긴 경우(
win), 진 경우(lose) 테이블을 만든다. 어떤 선수에 대해 이겼는지, 졌는지를 저장한다.1-1. 초기 테이블을 설정한다.
1-2. 추가적으로 “어떤선수 i를 이긴 j선수가 있을 때, j 선수를 이긴 사람들은 i 선수를 무조건 이긴다.”는 조건을 수행하도록 하는 테이블을 설정한다.
- 따라서 j선수를 이긴 사람들에게도 다 append해준다.
- 마찬가지로 진 선수인
i선수에게도 다 append한다.
1 2 3 4 5
for idx in range(1, n+1): for x in win[idx]: win[idx].update(win[x]) for x in lose[idx]: lose[idx].update(lose[x])
i번째 선수의win리스트와lose리스트의 길이를 더한 값이n-1이라면, 경기 결과를 알 수 있는 것이기 때문에answer += 1한다.
🚩My submission
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
def solution(n, results):
answer = 0
win = [[] for _ in range(n+1) ]
lose = [[] for _ in range(n+1) ]
cnt = 0
# 1. 테이블
# 1-1. 초기 테이블 설정
for w, l in results:
win[w].append(l)
lose[l].append(w)
# 1-2.추가 테이블 설정
for i in range(1, n+1):
for w in win[i]:
if lose[i]:
for l in lose[i]:
if l not in lose[w]:
lose[w].append(l)
if w not in win[l]:
win[l].append(w)
print(win, lose)
# 2. player 경기 기록에 대해서 카운트
for i in range(1, n+1):
cnt = len(win[i]) + len(lose[i])
if cnt == n-1:
answer += 1
return answer
[[], [2, 5], [5], [2, 5], [3, 2, 5], []] [[], [], [4, 3, 1], [4], [], [2, 4, 3, 1]]
🚩Others submission
나와 맥락은 같은데 비슷하게 더 가독성 좋게 짠 코드가 있어 첨부한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def solution(n, results):
answer = 0
win = [set() for i in range (n+1)] # i가 이긴 경우, 상대 선수
lose = [set() for i in range (n+1)] # i가 진 경우, 상대 선수
for a, b in results:
win[a].add(b)
lose[b].add(a)
for idx in range(1, n+1):
for x in win[idx]:
lose[x].update(lose[idx])
for x in lose[idx]:
win[x].update(win[idx])
for player in range(1, n+1):
count = len(win[player]) + len(lose[player])
if count == n-1:
answer += 1
return answer
그래프를 딕셔너리로 설정하는 JB 선배 방법
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
def solution(n, results):
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
플로이드 와샬
- 플로이드 와샬이 뭐였는지도 가물가물하지만, 이 방법으로도 풀 수 있다고 한다.
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):
matrix = [[None for _ in range(n)] for _ in range(n)]
for win, lose in results:
matrix[win-1][lose-1] = True
matrix[lose-1][win-1] = False
for i in range(n):
for j in range(n):
for k in range(n):
if matrix[j][i] == None:
continue
if matrix[j][i] == matrix[i][k]:
matrix[j][k] = matrix[j][i]
matrix[k][j] = not matrix[j][i]
answer = 0
for i in range(n):
if None in matrix[i][:i] + matrix[i][i+1:]:
continue
answer += 1
return answer
💡TIL
- 오타에 주의하자!! ( 오타나서,, 헤맸다.
- 어떤선수 i를 이긴 j선수가 있을 때, j 선수를 이긴 사람들은 i 선수를 무조건 이긴다. 여기서 i와 j를 어떻게 구할지가 모르겠다… (이게 핵심이라고 함) 어떤 성분을 for문으로 돌릴 것이냐가 관건이다. 이걸 할 때 for문에 많이 사용됨
- 그래프 문제는 안 풀리는 조건 하나가 있는데 그게 핵심인 것 같다.
- 저번 문제에서 그래프에 대해 조금 개념을 잡은 후에 하니까, 엄청 어렵지는 않았다.
💡 참고하면 좋은 블로그