프로그래머스. 순위

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

프로그래머스

 

전체 코드

정희경님 코드

# 예시 n = 5, results = [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]
def solution(n, results):
    answer = 0

    wins = [[] for _ in range(n + 1)]  # 1번 인덱스에는 1이 이긴(1에게 진) 선수가 담김
    loses = [[] for _ in range(n + 1)]  # 1번 인덱스에서는 1이 진(1에게 이긴) 선수가 담김

    for winner, loser in results:
        wins[winner].append(loser)
        loses[loser].append(winner)
    # wins = [[], [2], [5], [2], [3, 2], []]
    # loses = [[], [], [4, 3, 1], [4], [], [2]]

    for i in range(1, n + 1):
        for w in wins[i]:
            # 1 > 2 > 5 (1이 2에게 이겼다면, 2에게 진 애들도 모두 1이 이긴다)
            for a in wins[w]:
                if a not in wins[i]:
                    # 순회 중간에 append를 진행하면 해당 데이터를 포함해서 순회를 한다.
                    wins[i].append(a)
            # 한 바퀴 돌면 [[], [2, 5], [5], [2], [3, 2], []]
        for l in loses[i]:
            for b in loses[l]:
                if b not in loses[i]:
                    loses[i].append(b)
            # 3이 4에게 졌다면, 4에게 이긴 애들도 모두 3을 이긴다 (3이 짐)
    print(wins)
    print(loses)
    # wins = [[], [2, 5], [5], [2, 5], [3, 2, 5], []]
    # loses = [[], [], [4, 3, 1], [4], [], [2, 4, 3, 1]]

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

    return answer

 

선수의 순위를 결정하기 위해서는 모든 선수와 경기를 확인해야한다. 1 > 2, 2 > 5이면 1 > 5이 되며, 이처럼 승자, 패자와 연결된 노드를 순회하며 리스트에 추가하면 선수별 모든 선수와 경기했는지 확인할 수 있다.

승자, 패자를 그래프로 생성한 후 각 그래프를 순회하면서 해당 노드와 연결된 모든 노드를 리스트에 추가한다. 리스트에 중복된 부분은 pass한다. 순회 중에 append를 진행하면 추가된 데이터를 포함하여 순회한다.

승자, 패자 결과 리스트의 길이의 합이 n-1이면, 자신을 제외한 모든 선수와 경기를 했다는 의미이다. 순위 개수에 1을 추가하며 결과에 순위 개수를 반환한다.

 

인접 리스트 방식 및 set으로 풀이

def solution(n, results):
    winners = collections.defaultdict(set)
    losers = collections.defaultdict(set)

    for winner, loser in results:
        winners[winner].add(loser)
        losers[loser].add(winner)

    def get_linked_set(graph, v):
        # 시작 위치를 제외한 연결된 노드부터 탐색하기 위해 queue 초기화
        queue = collections.deque()
        for w in graph[v]:
            queue.append(w)

        visited = set()
        while queue:
            nv = queue.popleft()
            visited.add(nv)
            for nw in graph[nv]:
                if nw not in visited:
                    queue.append(nw)

        return visited

    for i in range(1, n + 1):
        winners[i] = get_linked_set(winners, i)
        losers[i] = get_linked_set(losers, i)

    answer = 0
    for i in range(1, n + 1):
        if len(winners[i]) + len(losers[i]) == n - 1:
            answer += 1

    return answer

인접 리스트 방식으로 딕셔너리를 초기화하였다. 여기서는 리스트가 아닌 set을 사용하여 중복된 값을 허용하지 않도록 하였다. 연결된 승자, 패자를 하나에 모을 때 BFS를 사용하여 순회하였고 방문한 set를 다시 그래프에 업데이트 하였다.