[프로그래머스] 순위 / Python

문제주소 :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                                               results                                         return

5

[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]

2

입출력 예 설명

2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.
5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.

 

<풀이법>

▒ 한줄 개념: Set ▒ 

문제를 푸는 방식은 다음과 같습니다.

 

1. 주어진 results를 이용하여 win, lose 딕셔너리 만들기

win은 {이긴 사람 : 진 사람들} 의 정보를 담고 있는 딕셔너리이고, lose는 {진 사람: 이긴 사람들} 의 정보를 담고 있는 딕셔너리 입니다. 두 딕셔너리에서 value로 들어가는 부분은 배열이 아닌 set() 자료구조로 만들어주어야 중복 방지뿐만 아니라 연산의 속도에서도 이점을 가져갈 수 있습니다. 배열로 구현할 경우 매번 중복처리를 해주지 않으면 시간 초과가 발생할 수 있습니다.

results : [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]

win : { 1: {2}, 2: {5}, 3: {2}, 4: {2, 3}, 5: {} }

lose : { 1: {}, 2: {1, 3, 4}, 3: {4}, 4: {}, 5: {2} }

 

2. 이긴사람의 이긴사람 모아주고, 진 사람의 진 사람 모아주기

a가 b를 이겼고, b가 c를 이겼다고 가정하면, a가 c를 이긴 셈이 됩니다. 반대로 c는 a에게 진 셈이 됩니다.

이러한 서로 이기고 지는 관계를 win, lose 딕셔너리를 탐색하며 전부 적용시켜줍니다.

초기 win : { 1: {2}, 2: {5}, 3: {2}, 4: {2,3}, 5: {} }

-> 바뀐 win : { 1: {2, 5}, 2: {5}, 3: {2, 5}, 4: {2, 3, 5}, 5: {} }

초기 lose : { 1: {}, 2: {1, 3, 4}, 3: {4}, 4: {}, 5: {2} }

-> 바뀐 lose : { 1: {}, 2: {1, 3, 4}, 3: {4}, 4: {}, 5: {1, 2, 3, 4}}

 

3. len( win[i] | lose[i] ) == n-1 이면 i는 순위가 명확한 것!

2단계에서 이기고 지는 모든 관계를 적용시켜줌으로서 win[i]에는 i를 이기는 모든 사람이 들어가 있고, lose[i]에는 i에게 지는 모든 사람이 들어가 있게 됩니다. 따라서 win[i]와 lose[i]의 합집합('|')연산의 결과가 n-1과 같다면, 이 i는 다른 모든 사람들과의 이기고 지는 관계가 설명이 되는 것입니다. 

다른 모든 사람들과의 이기고 지는 관계가 설명이 된다는 것은, 명확한 등수가 존재한다는 뜻이므로, answer += 1을 하게 됩니다.

 

<코드(Python)>

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 r in results:                     # 1단계
        win[r[0]].add(r[1])
        lose[r[1]].add(r[0])

    for key in win.keys():                # 2단계
        queue = win[key].copy()
        while len(queue) != 0:
            next_key = queue.pop()
            win[key] |= win[next_key]
            queue |= win[next_key]

    for key in lose.keys():
        queue = lose[key].copy()
        while len(queue) != 0:
            next_key = queue.pop()
            lose[key] |= lose[next_key]
            queue |= lose[next_key]


    for i in range(1, n+1):                # 3단계
        if len(win[i] | lose[i]) == n-1:
            answer += 1

    return answer

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest