[프로그래머스] 순위 (파이썬)

문제 출처: 프로그래머스

프로그래머스

 

문제 설명

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

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

출처: 프로그래머스

---

처음 문제를 읽었을 때는 어떻게 접근 해야할지 고민을 오래한 문제다.

 

내 생각의 흐름은 이랬다.

순위를 정하는 문제 ➡ sort문제 ➡ 하지만 sort의 key를 설정하기 어려움 ➡ Tree 형식으로 질 때 마다 자식 노드로 추가해주면 되지 않을까? ➡ 이렇게 됐을 때 구현은 어떻게 해야하나..

 

이런 식으로 생각을 이어가면서 깨작깨작 작성하다보니 정답에 도달할 수 있었다.

 

<정답 코드>

def solution(n, results):
    answer = 0
    rank = {i + 1: [set(), set()] for i in range(n)}
    order = [0] * (n + 1)

    for win, lose in results:
        rank[win][0].add(lose)
        rank[lose][1].add(win)

    for _ in range(2):
        for i in rank.keys():
            for wins in rank[i][0]:
                rank[i][0] = rank[i][0].union(rank[wins][0])

            for loses in rank[i][1]:
                rank[i][1] = rank[i][1].union(rank[loses][1])

    for i in rank.keys():
        if len(rank[i][0]) + len(rank[i][1]) == n - 1:
            answer += 1

    return answer

접근은 아래와 같다.

어떤 선수의 총 경기 횟수가 n-1이면 해당 선수의 순위를 알 수 있다. (비기는 경우는 없기 때문에)

1. 선수 번호를 기준으로 해당 선수가 이긴 선수들과 패배한 선수들을 기록하는 dictionary를 만든다.
   1. 딕셔너리의 value는 두 set의 집합으로 만들어진다.
   2. 0번 index는 해당 선수가 이겼던 선수들을 기록했고, 1번 index에는 해당 선수가 졌던 선수들을 기록했다.
2. 경기 결과를 하나씩 살피면서 rank를 채워준다.
3. 채워진 rank를 순회하면서 한번 이겼던 선수에게 패배한 선수들이 있다면 채워주는 작업을 반복한다.
   1. 예를 들어 results가 [3, 1], [1, 2]이었다고 하면 최초의 rank는 {1: [(2), (3)], 2:[(1), ()], 3:[(), (1)]}이 된다. 이 때 아래 for문을 통해 한번 순회해주면 rank는 {1:[(2), (3)], 2:[(1), (3)], 3:[(),(1, 2)]가 되게 된다.
4. 마지막으로 모든 선수들 중 총 경기횟수가 n-1번 진행된 선수들만 count해준다.

 

운이 좋게 위 코드에서는 rank를 채워주는 작업이 총 3번 만에 모든 test case가 통과되었지만, 곰곰히 다시 생각해보니 rank에 업데이트가 새로 일어나지 않을 때 까지 반복해서 업데이트해주어야 진짜 정답이지 않을까 했다. (아닐수도 있음)

 

이렇게 보니 트리라기 보다 그래프 문제에 가까워 보였다. 실제 문제를 보니 그래프 문제로 분류되어 있었고 다른 사람들은 bfs나 플로이드-와샬 알고리즘으로 문제를 해결했다고 했다. 독특한 풀이를 했다고 좋아하긴 했지만, 남들이 생각하는 걸 생각하지 못했다는 점에서 약간의 아쉬움도 있었다.

---

이번 문제를 통해서 드디어 프로그래머스 level3에 도달할 수 있었다.

여러 번 시도하면서 운 좋게 몇일 전에 풀어봤던 문제가 나오기도 하고, level 3치고 쉬운 문제가 나온 적도 있었지만 항상 다른 문제에서 막혀서 뚫지 못했었는데 이번에는 둘다 모르는 문제였지만 천천히 생각하면서 푸니 통과할 수 있었다.

 

프로그래머스의 level이 현재 내 코딩 수준을 정의해주는 것은 아니지만 (현재까지 프로그래머스 문제만 300문제 가까이 풀었지만, 아직도 풀지 못한 level2, level3문제가 많다.) 꾸준히 성장하고 있고, 꼼수 부리지 않고 통과하겠다는 의지가 먹혀든 것 같아서 기분이 좋았다.