문제의 레벨이 올라갈수록 입력이 커지면서 시간 초과에 벽에 자주 부딪히는 일이 발생하였다.
그런 일들을 줄여가기 위해 모아온 자료들을 정리해서 올려본다.
보통 입력을 받을 때 input() 메서드를 사용하지만, sys 모듈의 readline()을 사용하면 더 빠른 시간에 입력을 받을 수 있으며, 데이터가 많아질 수록 이 차이는 더 커진다.
똑같은 데이터를 반복적으로 리스트에 넣고 싶을 때, for 과 in range(n)을 사용할 수도 있지만, 곱셈 연산자를 사용하는 것이 더 빠르다.
그러나 여러 리스트를 만들 때에는 range 함수를 쓰도록 한다. 이는 리스트를 곱셈으로 만들 때에는 같은 참조를 하는 리스트 객체를 여러 개 만들기 때문에, 각 리스트가 다른 값을 담도록 하게 하고 싶을 때 한 리스트를 바꾸면 다른 모든 곱셈으로 만들어진 리스트들이 바뀌어지게 될 것이다.
import time
times = 100000000
start = time.time()
# for 과 in, range
i = [0 for _ in range(times)]
mid1 = time.time()
print(mid1-start)
# 곱셈 연산자
i = [0] * times
mid2 = time.time()
print(mid2-mid1)
출력
6.190709590911865
0.6791272163391113
큐를 구현할 때는 collections 모듈의 deque를 사용하고, 우선순위 큐를 구현할 때는 heapq