[문제 바로가기] https://programmers.co.kr/learn/courses/30/lessons/49191
📌문제 설명
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-1(본인 제외)과 같다면 해당 선수는 정확하게 순위를 매길 수 있다.
왜냐하면 자신을 기준으로 위 아래의 실력을 가진 모든 선수들이 누구인지 알기 때문에 자신의 위치는 자동적으로 정해진다.
step 1)
먼저, 자신보다 실력이 좋은 선수, 좋지 않은 선수를 분별하기 위해서 두 개의 딕셔너리를 정의하였다.
- win : 자신보다 실력이 좋은 선수를 담는다.
- lose : 자신보다 실력이 좋지 않은 선수를 담는다.
선수의 번호는 1부터 n까지 이므로 range(1, n+1) 범위에 해당하는 키-값 쌍을 만들어 놓는다.
이 때, 값으로 set 자료구조를 넣은 이유는 선수들의 실력관계가 1:1이 아닌 N:M이기 때문에 중복되는 선수의 번호가 담길 수 있다.
따라서, 중복처리를 쉽게하기 위해 set 자료구조를 사용하였다.
step 2)
results 배열에 담겨있는 경기 결과에 대해 win, lose 값을 최신화한다.
ex)
[4, 3] = 4번 선수가 3번 선수보다 실력이 좋다.
win[4] = 3 : 4번이 이긴 선수에 3번을 추가한다.
lose[3] = 4 : 3번은 자신을 패배시킨 4번 선수를 추가한다.
step 3)
results 배열에 담겨있는 경기 결과를 모두 탐색하였다면 이제는 모든 선수들을 순서대로 탐색하면서 우위관계를 파악한다.
ex)
만약 5 > 4 > 3 > 2의 관계가 있다고 가정했을 때
results가 [[5, 2], [5, 4], [4, 3], [3, 2]] 로 주어졌다면
2번 입장에서는 win[2] = {} / lose[2] = {5, 3} 가 된다.
하지만 우위관계를 살펴보면 2번을 패배시킨 3번보다 4번이 더 강하기 때문에 4번 역시 2번보다 강하다는 것을 확인하여 다음과 같이 최신화 시킬 수 있다.
win[2] = {} / lose[2] = {5, 4, 3}
※ lose 뿐만 아니라 win에 대해서도 위와 같은 경우가 생길 수 있으므로 동시에 진행한다.
step 4)
이제 특정 번호의 선수가 어떤 선수보다 실력이 좋은지, 좋지 않은지 win, lose를 통해서 알 수 있다.
처음 언급했듯이 win, lose에 담겨있는 선수의 합이 본인을 제외한 값인 n-1과 같다면 순위를 확정 지을 수 있다는 뜻이므로 answer+1 해준다.
코드는 다음과 같다.
def solution(n, results):
answer = 0
win = {i:set() for i in range(1, n+1)}
lose = {i:set() for i in range(1, n+1)}
for result in results:
A, B = result
win[A].add(B)
lose[B].add(A)
for i in range(1, n+1):
for loser in win[i]:
lose[loser] |= lose[i]
for winner in lose[i]:
win[winner] |= win[i]
for i in range(1, n+1):
if len(lose[i] | win[i]) == n-1:
answer += 1
return answer💡 TIL
처음에는 win, lose 내부에 set 자료구조가 아닌 list 자료구조를 사용하였다.
그리고 step 4)에 해당하는 단계에서 set()을 사용하여 중복처리를 하였는데
시간초과의 문제점이 발생하였다.
아무래도 우위관계를 파악하는 단계에서 중복되는 숫자가 많다보니 step 3)의 작업이 오래걸린 것 같다.
또한 list를 사용하였을 때는 '+'를 이용하여 list를 합쳤는데
for loser in win[i]:
lose[loser] += lose[i]set에서는 or 에 해당하는 |를 이용하여 |=로 += 연산을 대신할 수 있었다.
