파이썬 입출력 시간

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

1927번: 최소 힙

 

알고리즘 문제를 풀다보면 시간초과가 나는 경우가 더러 있다.

오늘 내 모습이다.

아무리 바꿔봐도 시간초과가 계속 나길래 뭐가 문제일까 하고 고찰을 시작했다.

제일 초기 코드 

import heapq

heap = []
n = int(input())

for _ in range(n):
    i = int(input())
    if i == 0:
        if heap:
            print(heapq.heappop(heap))
        else:
            print(0)
    else:
        heapq.heappush(heap,i)

 

제일 먼저 바꿔야 할 사항은 입력을 input()으로 받기보다는 sys.stdin.readline()으로 받는게 더 빠릅니다.

그리고 readline()으로 입력을 받으면 개행문자 ( \n")도 입력으로 받기 때문에, rstrip()으로 개행문자를 제거합니다.

1차 개선 코드

import heapq
import sys

heap = []
ans = ""
n = int(sys.stdin.readline().rstrip())

for _ in range(n):
    i = int(sys.stdin.readline().rstrip())
    if i == 0:
        if heap:
            ans += f"{heapq.heappop()}\n"
        else:
            ans += "0\n"
    else:
        heapq.heappush(heap,i)
print(ans)

 

근데 예전에 출력시 한 곳에 모아서 한번에 프린트하면 시간이 더 짧아진다고 들어서 이렇게 바꾸어 보았습니다.

많이 개선되었다고 생각했지만 또 시간초과가 나네요.

 

이 이후에 개선할 방법을 찾지 못해, 질문게시판을 가게 되었습니다.

https://www.acmicpc.net/board/view/130337

글 읽기 - 파이선 힙 직접구현 시간초과 나는 이유 도움 부탁드립니다 ㅠㅠ

요약하면, 내 경우에 ans라는 문자열 객체에 계속 저장을 하는데, 이 문자열 객체를 일일히 만드는데 시간이 오래 걸려서 시간초과가 난다 라는 것이었습니다. 

 

1. 매번 객체를 새로 만들어서 모아뒀다가 출력하는 경우와

2. 리스트에 저장했다가 한번에 출력하는 경우

3. 그 때 그 때 출력하는 경우 세가지 경우를 실제 코드로 실험해 본 분이 먼저 계시더라구요.

코드를 잠깐 가져와보았습니다.

코드

import time

n = 100_000
mx = 10  # 출력 결과 너무 클 수 있으므로 mx 까지만 출력..


def func1():  # 매번 객체 새로 생성
    output_str = ""

    for i in range(n):
        output_str += str(i) + '\n'

    print(output_str[:mx*2])


def func2():  # output_lst 에 저장했다가 마지막에 한 번에 출력
    output_lst = []

    for i in range(n):
        output_lst.append(str(i) + '\n')

    output_str = "".join(output_lst[:mx])
    print(output_str)


def func3():  # 그 때 그 때 출력
    for i in range(n):
        if i < mx:
            print(i)


print("func1 start..")
s = time.time()
func1()
e = time.time()
print("func1 end..")
print(f"func1 수행 시간 : {e - s}\n")


print("func2 start..")
s = time.time()
func2()
e = time.time()
print("func2 end..")
print(f"func2 수행 시간 : {e - s}\n")

print("func3 start..")
s = time.time()
func3()
e = time.time()
print("func3 end..")
print(f"func3 수행 시간 : {e - s}")

# func1 수행 시간 : 0.03298330307006836
# func2 수행 시간 : 0.025994539260864258
# func3 수행 시간 : 0.005004167556762695

 

그때그때 출력하는 것이 수행시간이 더 빠른 것을 알게 되었습니다! 

 

코테에서는 이런 입출력으로 인한 시간보다 알고리즘의 시간복잡도가 더 중요하다는 기술매니저님의 조언도 감사히 받은 하루였습니다!