[백준 2594번] 놀이공원 - 파이썬

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

2594번: 놀이공원

 

💡문제 분석 요약

놀이공원의 오픈 시간, 놀이기구 운행 시간, 마감 시간 사이 가장 쉬는 시간이 큰 시간을 구하라.

놀이기구의 운행 10분 전, 운행 10분 후까지는 쉴 수 없으며, 놀이기구의 운행 시간이 겹치는 경우에도 쉴 수 없다.

 

💡알고리즘 설계

1. 타임 리스트에 놀이공원의 오픈 시간과 놀이기구 운행 시작 시간, 종료 시간, 놀이공원 마감 시간을 타임스탬프 형식으로 변환하여 저장한다.

2. 타임 리스트를 정렬한다.

3. 다음 놀이기구의 시작 시간에서 현재 놀이기구의 종료 시간을 빼서 휴식 시간을 구하고, 휴식 리스트에 추가한다.

4. 휴식 리스트에서 가장 큰 값을 프린트한다.

 

💡코드

import sys
input = sys.stdin.readline

N=int(input())
time=0
time_list=[]
rest_list=[]

time_list.append([600, 600])
for _ in range(N):
    start, end = map(int, input().split())
    start=start//100*60+start%100-10
    end=end//100*60+end%100+10
    time_list.append([start, end])
time_list.append([22*60, 22*60])
time_list.sort()

last=600
for i in range(0, N+1):
    if last<time_list[i][1]:
        last=time_list[i][1]
    if last<time_list[i+1][0]:
        rest_list.append(time_list[i+1][0]-last)

print(max(rest_list))

💡시간복잡도

1. 타임 리스트 저장 -> O(N)

2. 휴식 리스트 저장 -> O(N)

3. 휴식 리스트에서 가장 큰 값 프린트 -> O(N)

 

💡 느낀점 or 기억할 정보

rest_list에 값을 하나씩 저장해서 max를 구하는 것 보다는, 매번 rest 값을 이전 값과 비교하여 더 큰 값으로 저장하는게 더 좋았을 것 같다.

시간의 계산 방법과, 다음 놀이기구가 끝나는 시간이 이전 놀이기구가 끝나는 시간보다 이른 경우를 고려해야한다.