백준 3665 최종순위 파이썬 풀이

난이도 : 골드1

풀이일 : 05081

https://www.acmicpc.net/problem/3665

3665번: 최종 순위

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

1차 시도 오답

import sys
from collections import deque

T = int(sys.stdin.readline().strip())
for _ in range(T):
    n = int(sys.stdin.readline().strip())    # 팀 수
    last = list(map(int, sys.stdin.readline().split()))    # 작년 등수
    m = int(sys.stdin.readline().strip())    # 등수 바뀐 팀 수
    child = deque([] for _ in range(n))
    count = [0] * n

    for i in range(n):
        for j in range(i+1, n):
            child[last[i]-1].append(last[j]-1)
            count[i] += 1

    flag = True
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        try:
            child[a - 1].append(b - 1)
            count[a - 1] -= 1
        except:
            flag = False
        try:
            child[b - 1].remove(a - 1)
            count[b - 1] += 1
        except:
            flag = False

    if flag:
        if m:
            queue = deque()
            for x in range(n):
                if not count[x]:
                    queue.append(x)
                    print(x + 1, end=' ')
            while queue:
                x = queue.popleft()
                for y in child[x]:
                    count[y] -= 1
                    if not count[y]:
                        queue.append(y)
                        print(y + 1, end=' ')
        else:
            print(*last, end=' ')
    else:
        print('IMPOSSIBLE')

    print()

코드 구성

• last : 작년 순위
• child : 각 팀 후순위에 해당하는 팀 번호
• count : 각 팀 선순위에 해당하는 팀 수
• flag : impossible 판별
• 작년 정보를 기준으로 child, count 설정
• 등수 바뀐 팀 정보를 받아 child, count 수정
  • 올해 등수는 a 팀이 높음(왼쪽) 기준
  • 만약 child, count 설정 과정에서 불가능하다면 flag = False
• queue 다음에 올 수 있는 요소들의 앞 팀 수 감소
  • 앞에 오는 팀이 0개라면 queue 추가

틀린 이유

• 맨 처음 입력 받는 과정 중 count[i] 오류 -> flag가 True 일 때, m 존재 여부를  파악하도록 끼워맞췄음

---

최종 정답

# 작년 팀 등수 정보로, 선행조건, 선행조건 수 저장
# 등수가 바뀐 팀들 정보 수정
# result 배열에 최종 순위 추가
# result 길이가 팀 수와 다르면 impossible 출력

import sys
from collections import deque

T = int(sys.stdin.readline().strip())
for _ in range(T):
    n = int(sys.stdin.readline().strip())    # 팀 수
    last = list(map(int, sys.stdin.readline().split()))    # 작년 등수
    m = int(sys.stdin.readline().strip())    # 등수 바뀐 팀 수
    child = deque([] for _ in range(n))
    count = [0] * n

    for i in range(n):
        for j in range(i+1, n):
            child[last[i]-1].append(last[j]-1)
            count[last[j]-1] += 1    # count[j]로 해둬서 틀림

    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        if a-1 in child[b-1]:
            child[a - 1].append(b - 1)
            count[a - 1] -= 1
            child[b - 1].remove(a - 1)
            count[b - 1] += 1
        else:
            child[b - 1].append(a - 1)
            count[b - 1] -= 1
            child[a - 1].remove(b - 1)
            count[a - 1] += 1

    result = []
    queue = deque()
    for x in range(n):
        if not count[x]:
            queue.append(x)
            result.append(x+1)

    while queue:
        x = queue.popleft()
        for y in child[x]:
            count[y] -= 1
            if not count[y]:
                queue.append(y)
                result.append(y+1)

    if len(result) == n:
        print(*result)
    else:
        print('IMPOSSIBLE')

코드 변화

• 주석으로 메모한 부분 count[last[j]-1] 수정
• 순위 변동 팀 정보 수정 코드 -> child 배열 해당 인덱스에 있는 지 확인 후 작업 선택 진행
• result : 기존 queue 삽입 요소 모두 출력 방식에서 리스트에 담아 출력하는 방식으로 수정
  • 최종 배열의 길이가 팀 수와 같은 경우에만 출력, 아닌 경우에는 impossible 출력을 위한 부분

---

느낀점

알고리즘 풀이에 시간 제한을 둬야겠다는 생각을 다시 한 번 했다.

어제는 세 시간 가까이 보이지 않았던 count[j] 실수가 오늘 아침에 보니 금방 보여서 허무하기도 하고 좋기도 했다.

또, 원래라면 티어를 보고 풀어보지도 않았을 문젠데, 티어를 안보고 일단 시작하고 나서 알게 되니까 할만하다고 느껴졌다.