백준 2623 음악프로그램 파이썬 풀이

난이도 : 골드3

풀이일 : 2401221

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

2623번: 음악프로그램

---

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

---

풀이 코드

import sys
from collections import deque

N, M = list(map(int, sys.stdin.readline().split()))

# 본인 이전 가수의 수
previousN = [0 for _ in range(N + 1)]

# 본인 이후 가수 번호
nextN = [[] for _ in range(N + 1)]

# 정답을 담을 queue
result = deque()

# 순서 탐색을 위한 queue
queue = deque()

# 입력
for _ in range(M):
    temp = list(map(int, sys.stdin.readline().split()))
    # 보조 PD 담당 수는 제외하고 인덱스 1부터 끝까지 정보 입력
    for i in range(1, len(temp) - 1):
        for j in range(i + 1, len(temp)):
            previousN[temp[j]] += 1
            nextN[temp[i]].append(temp[j])

# 이전 가수가 없으면 queue에 추가
for i in range(1, N + 1):
    if not previousN[i]:
        queue.append(i)

while queue:
    x = queue.popleft()
    # 출연 순서대로 result에 추가
    result.append(x)

    # 내 다음에 부를 가수들의 previous 값 줄이기
    for nx in nextN[x]:
        previousN[nx] -= 1
        # 더 이상 먼저나올 가수가 없다면 queue에 추가
        if not previousN[nx]:
            queue.append(nx)

# result의 길이가 N과 같아 모두 출연했다면 출연 순서대로 출력
if len(result) == N:
    while result:
        print(result.popleft())
else:
    print(0)

• previosN : 내 앞에 나와야 하는 가수가 몇 명인지 기록
• nextN : 내 다음에 출연하는 가수들의 정보를 기록
  • 어제 문제 풀이에서는 next 이름을 사용했는데, 내장함수랑 이름이 겹치지 않도록 수정
• result : 출연 순서를 결정할 수 없는 경우가 존재하므로, queue 탐색으로 찾은 출연 순서를 저장할 queue
• queue : 출연 순서를 탐색할 queue
• 보조 PD별 결정한 출연 순서 정보 저장
  • 주의 '맨 앞 숫자는 다룰 가수의 수'
  • 이중 반복문을 통해 모든 가수에 대한 출연 선후 정보를 저장
• 먼저 출연할 가수가 없다면, queue에 추가
• queue에서 가수를 popleft 할 때, result에 저장하여 순서 기록
• 현재 출연 가수 x 뒤에 출연할 가수 nx 들의 previousN 숫자 - 1
  • 만약 먼저 출연해야할 가수들이 모두 출연한 경우, 출연할 가수 nx에 추가
• result의 길이가 N과 같아 모든 가수들이 출연했다면, 순서대로 출력
• result의 길이가 N과 같지 않을 경우, 0 출력

---

느낀점

• 어제의 문제랑 비슷한데 정렬때문에 문제의 난이도가 다르게 매겨진건가 궁금하다.
• 주석을 달고, 내가 생각한 것들을 상세히 기록하니까 시간은 조금 더 걸려도 더 재밌는 것 같다.
• 여행가서도 난이도 적절하게 섞어서 꾸준히 풀 수 있도록 해야지