민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다.
어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다.
N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 풀어야 한다. 예를 들어서 네 개의 문제가 있다고 하자. 4번 문제는 2번 문제보다 먼저 푸는 것이 좋고, 3번 문제는 1번 문제보다 먼저 푸는 것이 좋다고 하자. 만일 4-3-2-1의 순서로 문제를 풀게 되면 조건 1과 조건 2를 만족한다. 하지만 조건 3을 만족하지 않는다. 4보다 3을 충분히 먼저 풀 수 있기 때문이다. 따라서 조건 3을 만족하는 문제를 풀 순서는 3-1-4-2가 된다.
문제의 개수와 먼저 푸는 것이 좋은 문제에 대한 정보가 주어졌을 때, 주어진 조건을 만족하면서 민오가 풀 문제의 순서를 결정해 주는 프로그램을 작성하시오.
첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주어진다. 이는 A번 문제는 B번 문제보다 먼저 푸는 것이 좋다는 의미이다.
항상 문제를 모두 풀 수 있는 경우만 입력으로 주어진다.
첫째 줄에 문제 번호를 나타내는 1 이상 N 이하의 정수들을 민오가 풀어야 하는 순서대로 빈칸을 사이에 두고 출력한다.
입력 1
4 2
4 2
3 1
출력 1
3 1 4 2
문제 간에 선수 관계가 존재하는 조건으로 인해, 다양한 선수 관계가 발생 가능한 상황의 예제를 만들었습니다.
5->7->4
7->1
9->1
3->6->2
모든 숫자를 출력해야 하는데, 매 iteration마다 출력하는 수는 '해당 iteration에서 풀 수 있는 가장 쉬운 문제'였습니다.
이것은 달리 말해서, '선행되는 수가 없는 가장 작은 수'를 출력하는 문제였던 것입니다.
결국 '선행되는 수가 없는 수'들을 담은 heap에서 지속적으로 가장 작은 수를 출력하면 정답입니다.
문제 간단 요약: 1~N까지의 수를 작은 순서대로 나열하면 됩니다.
BUT 어떤 수는 다른 수보다 먼저 등장해야 합니다. (= 숫자 간에 선수 관계 존재)
가능한 상황: 1: [7, 9] -> 1이 나오기 전에 7과 9가 나와야 함. 4: [7 ] -> 4가 나오기 전에 7이 나와야 합니다.
초기 세팅: 선-후 관계에 대한 dictionary, 후-선 관계에 대한 dictionary, '선행되는 수가 없는 수'들을 담은 heap => 총 3개의 자료구조를 준비합니다.
if __name__ == '__main__':
N, M = map(int, input().split())
R = [tuple(map(int, input().split())) for _ in range(M)]
BA, AB = defaultdict(list), defaultdict(list) # Before-After, After-Before
for a, b in R:
BA[a].append(b)
AB[b].append(a)
hq = [val for val in range(1, N + 1) if val not in AB]
heapq.heapify(hq)heap pop을 하면서 선행되는 수가 없는 수 중 가장 작은 값 nxt를 answer 배열에 저장합니다.
또한, nxt가 선행되는 수인 수 중에서, nxt를 제거하고 나서 선행되는 수가 수 val을 heap에 저장합니다.
answer = []
while(hq):
nxt = heapq.heappop(hq)
answer.append(nxt)
if nxt in BA:
for val in BA[nxt]:
AB[val].remove(nxt)
if len(AB[val]) == 0:
heapq.heappush(hq, val)
BA.pop(nxt)
print(*answer)여기까지 진행했을 때, 배열 내의 특정 원소를 제거하는 remove 연산이 O(N)의 시간복잡도를 가지는 것이 시간 초과를 야기할 것으로 예상하고 입력의 크기를 고려해서 연산 횟수를 대략적으로 생각해봤습니다.
while문에서 hq는 N개의 수가 저장되서 while문은 총 N번 실행됩니다.
remove 연산은, 어떤 수가 N개의 수를 선행되는 수로 가질 수 있기 때문에 최대 N번의 연산이 발생할 수 있습니다.
따라서 시간 복잡도는 O(N^2)이 되고, 이는 32000^2으로 대략 9억번의 연산이 최대로 소요됩니다.
O(N)의 시간 복잡도를 가지는 remove 연산을 O(1)로 해결하기 위해 AB dictionary의 value가 선행되는 수 list가 아닌, 선행되는 수의 개수로 바꾸고, 선행되는 수를 하나를 heap에서 pop할 때마다 1씩 지웠습니다.
수정된 코드:
if __name__ == '__main__':
N, M = map(int, input().split())
R = [tuple(map(int, input().split())) for _ in range(M)]
BA, AB = defaultdict(list), defaultdict(int) # Before-After, After-Before
for a, b in R:
BA[a].append(b)
AB[b] += 1
hq = [val for val in range(1, N + 1) if val not in AB]
heapq.heapify(hq)
answer = []
while(hq):
nxt = heapq.heappop(hq)
answer.append(nxt)
if nxt in BA:
for val in BA[nxt]:
AB[val] -= 1
if AB[val] == 0:
heapq.heappush(hq, val)
BA.pop(nxt)
print(*answer)- 낯선 문제는 다양한 상황을 커버하는 예제를 만들어서 접근해본다.
- 이를 통해 edge 케이스를 생각해보고
- 문제 해결의 실마리를 찾을 수 있다.
- 매 순간 가장 작은 수를 출력해야 하고, 수가 저장된 배열이 자주 바뀐다면 heap 사용을 고려해보자.
import sys
input = sys.stdin.readline
import heapq
from collections import defaultdict
if __name__ == '__main__':
N, M = map(int, input().split())
R = [tuple(map(int, input().split())) for _ in range(M)]
BA, AB = defaultdict(list), defaultdict(int) # Before-After, After-Before
for a, b in R:
BA[a].append(b)
AB[b] += 1
hq = [val for val in range(1, N + 1) if val not in AB]
heapq.heapify(hq)
answer = []
while(hq):
nxt = heapq.heappop(hq)
answer.append(nxt)
if nxt in BA:
for val in BA[nxt]:
AB[val] -= 1
if AB[val] == 0:
heapq.heappush(hq, val)
BA.pop(nxt)
print(*answer)