[그래프] 순위 - Level 3 (프로그래머스)

순위

문제 소개

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

시나리오

1. 입력 받은 경기 결과를 보기 쉽게 정리한다.

   • 4번이 3번을 이겼으면, 3번은 4번에게 졌다. (wins, loses)

2. 저장된 경기 결과들을 토대로 절대적인 경기 결과를 추가한다. 예를 들어

   • 1번이 2번을 이겼다면, 2번은 1번이 진 3번에게도 진다.
   • 4번이 5번에게 졌다면, 5번은 4번이 이긴 6번에게도 이긴다.

# 아래로 보세요.

## 첫 번째 예시         ## 두 번째 예시
# 제 1 경기 
    3번 (승)            5번 (승)    
    1번 (패)            4번 (패)

# 제 2 경기 
    1번 (승)            4번 (승)
    2번 (패)            6번 (패)

------------          ------------
# 도출된 결과
    3번 (승)            5번 (승)
    2번 (패)            6번 (패)

3. 이긴 경기 수와 진 경기 수의 합이 자신을 제외한 n-1과 같다면 모든 선수와 경기를 한 것이다. 즉, 해당 선수의 순위를 확신할 수 있다.

고민된 점

시나리오 2번을 구상할 때 고민되는 부분이 있었다. 내가 선수 1번이고 선수 2번을 이겼을 때,

1. 2번 선수를 이겼으니, 2번 선수가 이긴 선수도 내가 이긴다.

   • 1번의 이긴 경기 이력에 2번 선수가 이긴 선수들을 포함

2. 2번 선수를 이겼으니, 1번(나)이 진 선수들은 2번도 진다.

   • 2번의 진 경기 이력에 1번(나)의 진 선수들을 포함.

이 두 가지 경우이다. 비슷해보이지만 경기 이력 반영을 나에게 하느냐, 이기거나 진 선수에게 하느냐의 차이가 있다.

말로 써내려갔을 땐 결국 모두 추가되니깐 결과는 같을 것이라 생각했다. 하지만 첫 번째 경우 테스트 케이스 2,7,8,9에서 실패가 발생한다.

원인을 분석해보면 반복문으로 선수를 하나씩 살펴보면서 해당 경우들을 반복문으로 추가할 때, 자신의 인덱스 위치에서 자신의 승리, 패배 이력에 추가하게 되면(첫 번째 경우) 먼저 추가한 선수일 수록 추후에 시행되는 결과물들이 반영되지 않는다. 즉, 미완성된 경기이력을 가지고 반영한 꼴이 된다.

때문에, 자신의 인덱스 위치에서 자신이 승리한 선수 또는 패배한 선수의 경기 이력을 갱신해줘야 한다.

말이 복잡하지만 두 경우를 모두 구현해보면 차이점이 나타날 것이다.

또 다른 꼼수?로는 서로의 경기 이력들을 반영하는 과정을 2번씩 반복하면 풀리긴 한다.😀 하지만 시간복잡도에서 좋지 않으니 PASS~

문제 풀이

def solution(n, results):
    answer = 0
    wins = [set() for _ in range(n+1)]
    loses = [set() for _ in range(n+1)]
    
    for A, B in results:
        wins[A].add(B)
        loses[B].add(A)

    for i in range(1,n+1):
        for loser in wins[i]:
            loses[loser] |= loses[i]
        for winner in loses[i]:
            wins[winner] |= wins[i]
            
    for w in range(1,len(wins)):
        if len(wins[w]) + len(loses[w]) == n - 1:
            answer += 1

    return answer