BaekJoon 3665번 : 최종 순위 (python)

📝 BaekJoon 3665번 : 최종 순위 (G1 38.532%)

---

🔎 최종 순위 문제

---

📌 아이디어

위상정렬 알고리즘 문제로 진입차수만 확인하면 되는 문제이지만 작년의 순위에서 변동된 올해의 순위를 어떻게 관리할 것인지가 관건인 문제이다.

---

💭 풀이

• 먼저 처음에 주어지는 작년의 순위를 통해 진입차수를 미리 계산해놓을 수 있다. 현재 인덱스의 값은 뒤의 인덱스 값 보다 우선순위가 높기 때문에 뒤에 오는 인덱스 값 들의 진입차수를 1씩 더해준다.
• 이후에 상대적인 등수가 바뀐 쌍 (a,b)가 주어질 때 a,와 b의 작년의 순위를 비교하여 작년의 순위가 더 작은 팀의 진입차수를 1 더해주고 작년의 순위가 더 큰 팀의 진입차수는 1을 빼준다.
• 그렇게 올바르게 정렬이 되었다면 진입차수는 0부터 n-1까지의 원소가 1개씩 존재할테고 해당 원소의 index + 1순서대로 정렬된 순서가 된다.
• 만약 0부터 n-1까지의 원소가 1개씩 존재하지 않을 경우 데이터에 일관성이 없어서 순위를 정할 수 없는 경우이므로 'IMPOSSIBLE'을 출력해준다.

---

💻 코드

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T) :
    n = int(input())
    node = list(map(int,input().split()))
    m = int(input())
    
    index = [-1]*(n+1)
    for i in range(len(node)) :
        index[node[i]] = i
    
    indegree = [0]*(n+1)
    for i in range(len(node)) :
        for j in range(i+1, len(node)) :
            indegree[node[j]] += 1
    
    for _ in range(m) :
        a, b = map(int,input().split())
        if index[a] < index[b] :
            indegree[b] -= 1
            indegree[a] += 1
        else :
            indegree[a] -= 1
            indegree[b] += 1
    
    indegree.pop(0)
    if len(set(indegree)) != len(indegree):
        print('IMPOSSIBLE')
    else :
        result = []
        for i in range(n) :
            result.append(indegree.index(i) + 1)

        print(*result)

---