백준 1766 문제집 파이썬 풀이

난이도 : 골드2

풀이일 : 2401217

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

1766번: 문제집

---

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

---

풀이 코드

import sys, heapq

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

# 먼저 거쳐야 하는 문제 수
previous = [0 for _ in range(N + 1)]

# 다음에 풀 문제 번호
next = [[] for _ in range(N + 1)]

for _ in range(M):
    p, s = list(map(int, sys.stdin.readline().split()))
    previous[s] += 1
    next[p].append(s)

queue = []
for i in range(1, N + 1):
    # 먼저 풀어야하는 문제가 없는 번호를 큐에 추가
    if not previous[i]:
        heapq.heappush(queue, i)

while queue:
    # 힙큐로 가장 작은 번호를 반환, 출력
    now = heapq.heappop(queue)
    print(now, end=" ")
    
    # 해당 문제 후 풀 문제들의 선행문제 조건 변경
    # 먼저 풀어야 하는 문제를 다 풀었다면, 큐에 추가
    if next[now]:
        for j in next[now]:
            previous[j] -= 1
            if not previous[j]:
                heapq.heappush(queue, j)

• previous : 현재 문제를 풀기 전, 풀어야 하는 문제의 수
• next : 해당 문제 다음에 풀 문제들의 번호를 저장할 리스트
• 각 문제들의 선행 문제를 먼저 풀어야 하는 동시에 가능하다면 쉬운 순서대로 풀이해야 해서 정렬을 위한 힙큐 사용
• 먼저 풀어야 하는 문제가 없는 번호들을 힙큐에 추가
• 방문하는 문항을 조건에 맞추어 출력
• 해당 문제 다음에 풀 문제들의 previous 값 차감 후, previous가 0이 된 문제들은 힙큐에 추가

---

추가 오답 코드 -> 12% 시간 초과

import sys
from collections import deque

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

# 먼저 거쳐야 하는 문제 수
previous = [0 for _ in range(N + 1)]

# 다음에 풀 문제 번호
next = [[] for _ in range(N + 1)]

for _ in range(M):
    p, s = list(map(int, sys.stdin.readline().split()))
    previous[s] += 1
    next[p].append(s)

queue = deque()
for i in range(1, N + 1):
    # 먼저 풀어야하는 문제가 없는 번호를 큐에 추가
    if not previous[i]:
        queue.append(i)

while queue:
    queue = sorted(queue)
    queue = deque(queue)
    now = queue.popleft()
    print(now, end=" ")

    if next[now]:
        for j in next[now]:
            previous[j] -= 1
            if not previous[j]:
                queue.append(j)

코드 변화

• heapq 대신 deque를 사용
• deque 정렬을 위해 이상한 방법을 시도했는데, 직접 정렬이 안되는 것 같아서 아래와 같이 정렬했다.
  • queue = sorted(queue)로 리스트 큐를 정렬해서 queue 재할당
  • queue = deque(queue)로 다시 deque 형태로 변환 후 재할당 
• 위 정렬 과정에서 모든 queue 요소를 하나씩 popleft 할때마다 큐를 새로 정렬하니까 시간 복잡도가 상승한다.
• 혹시나 queue에 요소를 넣을 때만 정렬을 하면 시간이 덜들어서 통과가 되려나 해봤는데, 역시나 12%에서 시간초과 발생

---

느낀점

• 예전에 비슷한 유형의 문제들을 풀었던 적이 있어서 쉽게 풀 수 있었다. 어제 오늘은 계속 한 번에 통과해서 굉장히 기분이 좋은 상태!
• 힙큐를 사용하지 않았다면, deque를 쓰고 매번 정렬을 했을 것 같은데, 그래도 되는지 궁금하니까 당장 해봐야지 (추가 오답 코드 참고)
• 혹시나 되나 싶었는데 안되네! 골드2 문젠데 다른 문제들에 비해 쉽다고 느껴지는데, heapq 안써봤을 때에는 엄청 헤매고 틀리고 했을 것 같긴 하다.
• 역시 알고리즘은 습관이 되면 재밌어