[Python] 시간 초과 해결 방법

알고리즘 문제를 풀다 보니 예제는 다 맞는데 시간초과로 틀리는 경우가 많아 해결법을 정리해보았다.

 

1. input() -> sys.stdin.readline()

 

input()보다 훨씬 빠른 시간에 적은 메모리를 사용하여 입력 받을 수 있다.

import sys
변수 = sys.stdin.readline()

 

2. queue -> deque

 

리스트보다 collections.deque 모듈을 사용하는 것이 더 빠름

que.pop(0)을 실행하면 맨 앞 값을 삭제 후 모든 값을 1칸 씩 앞으로 당겨야함

deq.popleft()는 맨 앞 값 삭제만 함

# queue
que = []
# 삽입
que.append('넣고 싶은 값')
# 첫번째 값 삭제
que.pop(0)

# deque
from collections import deque
deq = deque()
# 삽입
deq.append('넣고 싶은 값')
# 첫번째 값 삭제
deq.popleft()

 

3. list -> set

 

삽입(insert, pop), 제거(delete, remove), 탐색(check ==, ≠), 포함 여부 확인(containment)의 경우

 -> List 자료형에서는 모두 시간 복잡도 O(N)

 -> Set과 Dict는 모두 O(1)의 시간 복잡도