[Python] 백준 15748번: snow boots (백준 Python 입력 시간 줄이기, input()과 sys.realine()의 시간 차이)

문제

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

15748번: Rest Stops

농부 John과 그의 트레이너 Bessie가 산행을 하는데, Bessie가 얻을 수 있는 최대 taste를 찾는 것이다. 문제에서 Bessie는 쉬면서 맛있는 풀을 먹을 있지만 항상 John보다 앞서있어야한다는 조건이 있다. 이는 Bessie가 항상 John보다 빠르다는 제약이 있기 때문에 가능한 문제이다.

 

입력은 두 줄이며, 첫 줄에는 전체 산행 길이, 쉴 수 있는 포인트 개수, John의 미터 당 시간, Bessie의 미터 당 시간이 들어오고, 두 번째 줄에는 쉴 수 있는 포인트의 위치와 해당 위치에서 얻을 수 있는 taste 정보가 주어진다.

 

설명

문제는 비교적 간단한 편이다.  Bessie가 얻을 수 있는 전체 taste가 높이는 방법은 Bessie는 최대 taste를 얻을 수 있는 곳에서 오래 머무르는 것이다. 다만, 항상 John보다 앞서야한다는 제약이 있으므로 문제는 John이 오기전까지 가장 높은 taste가 있는 곳에서 최대한 머문다로 바꿀 수 있다. 이 경우, taste가 높은 순서대로 sorting한 후 John이 오기전까지 최대한 머무르는 코드를 짜면 쉽게 풀 수 있다. sorting이 들어가기 때문에 N*log(N)의 시간복잡도를 가지고 있다. (여담이지만, N의 복잡도로도 풀 수 있는 방법이 있는데 내 아이디어가 아님으로 패스,,)

코드

L, N, rF, rB = map(int, input().split())
rest_pos = []
for i in range(N):
    x, c = input().split()
    rest_pos += [(int(x), int(c))]
    
ans = max_point = 0;

for p in sorted(rest_pos, key=lambda x:x[1], reverse=True):
    x,c = p
    if x < max_point:
        continue
        
    available = (x-max_point) * (rF-rB)
    ans += available * c
    max_point = x

print(ans)

입력을 받은 후, taste 기준으로 정렬하여 반복문을 돈다. max_point는 Bessie의 현재 위치이고, x가 현재 위치보다 작은 곳(즉, 지나 온 곳)이라면 무시해도 된다. available은 말 그대로 쉴 수 있는 시간이고, 나아갈 위치(x)에서 현재 위치(max_point)를 빼면 갈 거리 (meter)가 나오는데 거기서 John과 Bessie의 미터 당 걸리는 시간 차이를 곱해주면 구할 수 있다. 

 

import sys

# L, N, rF, rB = map(int, input().split())
L, N, rF, rB = [int(x) for x in sys.stdin.readline().split()]
rest_pos = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]    
ans = max_point = 0;

for p in sorted(rest_pos, key=lambda x:x[1], reverse=True):
    x,c = p
    if x < max_point:
        continue
        
    available = (x-max_point) * (rF-rB)
    ans += available * c
    max_point = x

print(ans)

이 문제를 풀고 알게된 사실인데, input()을 통한 입력받기는 굉장히 오랜 시간이 걸린다. 대신 sys module을 통해 sys.readline()을 이용하면 입력받는 시간을 극적으로 줄일 수 있다.

 

결과

앞서 얘기했다시피, input() -> sys.readline()을 변경했을 뿐인데 시간이 약 1/20 줄었다... input()을 이용했을 때는 시간 초과 걸리기 쉽상이다.