[프로그래머스] LEVEL3 순위 (Python)

[프로그래머스] LEVEL3 순위

---

🧐 문제 설명

---

😍 나의 풀이

문제가 그래프라고 명시되어 있기 때문에 딕셔너리를 이용해서 풀어야겠다고 생각했다. 선수별로 이긴 선수 SET과 진 선수 SET을 구성하는 딕셔너리 2개를 만든다. 초기에 알고 있는 정보들을 바탕으로 SET에 이겼는지, 졌는지를 원소에 추가해주는 것은 쉽다.

그래프로 처음 주어진 정보 results로 승리 관계를 표현하면 다음과 같다.

• A에게 이긴 선수는 A에게 진 선수에게도 이긴다.
• A에게 진 선수는 A에게 이긴 선수에게도 진다.

이러한 승패 관계를 코드로 논리적으로 표현하는 것이 이 문제의 핵심이다.

예를 들어서, 4번은 2번에게 승리하고 2번은 5번에게 승리하기 때문에 4번은 5번에게도 승리한다. 바꿔 말해서, 5번은 2번에게 패배하고 2번은 4번에게 패배하기 때문에 5번은 4번에게도 패배한다.

4 → 2 → 5 => 4 → 5 (WIN)
5 → 2 → 4 => 5 → 4 (LOSE)

따라서, 이긴 선수 집합을 최신화하기 위해서 진 선수 집합의 VALUE인 이긴 선수들을 KEY로 하는 이긴 선수 집합에 진 선수가 이긴 선수를 추가한다. 즉, 예를 들어 2번이 졌다면 2번에게 이긴 1, 3, 4를 KEY로 하는 이긴 집합에 2번이 이긴 원소(5)를 추가한다.
→ 이걸 논리적으로나 코드로 표현하는 게 상당히 까다로웠다...

'진 선수 집합'도 마찬가지로 update해준다. 선수별로 이긴 선수 집합의 크기와 진 선수 집합의 크기의 합이 자신을 제외한(-1) 선수 크기 n-1 이라면 자신의 등수를 명확히 알 수 있기 때문에 answer를 +1 해준다.

def solution(n, results):
    answer = 0
    win_dict, lose_dict = {}, {}    # 이긴 선수 집합, 진 선수 집합
    
    for i in range(1, n+1):
        win_dict[i] = set()
        lose_dict[i] = set()
        
    for win, lose in results:   # 초기 정보
        win_dict[win].add(lose)
        lose_dict[lose].add(win)
        
    for i in range(1, n+1):
        for winner in lose_dict[i]: # 진 선수가 이겼으면 이긴 선수도 이김
            win_dict[winner].update(win_dict[i])
        for loser in win_dict[i]:   # 이긴 선수가 졌으면 진 선수도 짐
            lose_dict[loser].update(lose_dict[i])
        
    for i in range(1, n+1):
        if len(win_dict[i]) + len(lose_dict[i]) == n-1:
            answer += 1
    
    return answer

---

🥇 Today I Learn

set(집합)의 update

• set에서 여러 데이터를 한번에 추가할 때 사용

>>> k = {1, 2, 3}
>>> k.update([3, 4, 5])
>>> k
{1, 2, 3, 4, 5}