2.2.2 시간 복잡도 줄이기

시간 복잡도 예측 방법을 대략 알았다면 이번에는 더 빠르게 실행하는 코드를 짤 수 방법을 알아보겠습니다.

지금까지 알고리즘의 시간 복잡도를 줄이는 방법은 ‘입력 개수를 보고 그에 맞는 적절한 알고리즘 선택한다’, ‘자료형이나 자료 구조를 적극적으로 사용한다’, ‘반복문을 줄인다’ 등 직접적으로 연산량 자체를 줄이는 방법만 살펴봤습니다. 하지만 코딩 테스트는 그리 만만치 않습니다. 이 모든 사항을 고려했는데도 불구하고 시간 초과가 발생하거나 예상하지 못한 입력값으로 실패하는 경우가 흔합니다. 이번에서는 파이썬에서 주의해야 할 점과 시간 복잡도를 줄이도록 코드를 짜는 방법에 대해 알아보겠습니다.

readline( ): 입력 속도를 빠르게

코딩 테스트마다 입력값을 제공하는 방법이 다릅니다. 프로그래머스의 경우 입력값을 모두 주고, 원하는 기능만 구현하면 되는 함수 형태로 시작 코드가 주어지지만, 실제 테스트를 볼 때는 입력값을 받는 코드도 직접 구현해야 하는 경우가 있습니다.

이럴 때는 sys 모듈의 readline()을 활용합니다. 파이썬으로 값을 입력받을 때는 input()을 사용한다고 배웠지만, 이 함수는 데이터가 많을수록 효율이 떨어집니다. 받은 문자열을 다시 쪼개더라도 readline() 함수를 사용하여 빨리 읽어오는 게 훨씬 효율적입니다.

import sys
data = sys.stdin.readline()