[프로그래머스] 순위

https://programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

 

주어진 results 배열로 해당 선수보다 순위가 낮은 선수들의 집합과 높은 선수들의 집합을 구하여 순위를 결정할 수 있으면 answer 에 1 씩 더하였다. 

 

예를 들어, 순위 관계가 A < B 라고 가정하자.

 

문제에서 A < B 라면 results 배열에 [B, A] 가 존재하거나, A=C0 < C1 < C2 < ... < Cn-1 < B=Cn 를 만족하는 [C1, A], [C2, C1], ... , [B, Cn-1] 이 존재한다.

 

아래의 소스에서 i 에 해당하는 것이 Cm 이라고 한다면

W -> Cm-1 : {Cm, Cm+1}

L -> Cm+1 : {Cm, Cm-1}

 

이렇게 되면 다음에 i 에 해당하는 것이 Cm-1 일 때, Cm 은 Cm-2 와의 관계가 정리될 것이고 Cm+1 이 나오면 Cm+2 와의 관계가 정리된다. 다음에 i 에 해당하는 것이 Cm-2 라면 Cm 은 Cm-3, Cm+2 라면 Cm+3 과 관계가 정리된다.

Cm-2 가 Cm-1 보다 먼저 나올 때는 Cm-1 이 Cm-3 과의 관계가 정리되기 때문에 Cm-1 이 나올 때는 Cm 과 Cm-3 의 관계가 정리된다.

 

솔직히 설명을 제대로 하고 있는지 모르겠지만, 하고 싶은 말은 아래의 소스로 모든 관계가 표현된다는 것을 말하고 싶었다.

 

from collections import defaultdict

def solution(n, results):
    answer = 0
    W = defaultdict(set)
    L = defaultdict(set)
    
    for i, j in results:
        W[j].add(i)
        L[i].add(j)
    
    for i in range(1, n+1):
        for j in W[i]:
            L[j] = L[j].union(L[i])
        
        for j in L[i]:
            W[j] = W[j].union(W[i])
    
    for i in range(1, n+1):
        if len(W[i].union(L[i])) == n - 1: answer += 1

    return answer

print(solution(5, [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]])) # 2