[Python] 백준 2594 놀이공원 (구현)

 

📌 문제

놀이공원에서 여러 개의 놀이기구를 맡아 일하는 세혁이와 근영이는 서로 좋아하는 사이이다. 그들은 쉬는 시간을 이용하여 둘만의 시간을 가지기를 원한다. 그래서 매일 일과 시작 전에 놀이기구의 운영 일정을 보고, 그날 둘이 함께할 수 있는 가장 긴 휴식시간이 언제인지를 찾으려고 한다.

 

놀이공원에서 일하는 모든 사람들은 어떤 놀이기구가 작동을 시작하기 10분 전부터, 모든 놀이기구가 작동을 멈춘 후 10분 후까지는 쉴 수 없고, 그 나머지 일과 시간에만 쉴 수 있다.

 

하루 일과를 시작하는 시각은 오전 10시이고, 일과를 마치는 시각은 오후 10시이다. 예를 들어 세 개의 놀이기구가 작동하는 시간이 다음과 같다고 하면,

 

놀이기구 1: 오전 10시 30분 - 오후 1시
놀이기구 2: 오후 7시 00분 - 오후 9시 10분
놀이기구 3: 오후 12시 30분 - 오후 4시 50분

세혁이와 근영이는 놀이기구 1이 운행되기 전에 20분, 놀이기구 3의 운행이 끝나고 놀이기구 2의 운행시작 전 사이에 1시간 50분, 놀이기구 2의 운행이 끝난 후에 40분 동안 쉴 수 있다. 따라서 둘이 함께할 수 있는 가장 긴 시간은 1시간 50분이다.

놀이기구 운영 일정이 주어질 때, 그 날 세혁이와 근영이가 함께할 수 있는 가장 긴 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 놀이기구의 개수 N이 주어진다. 이어 N줄에 걸쳐 각 놀이기구의 운행시작 시각과 종료 시각이 빈 칸을 사이에 두고 주어진다. 시각은 시간단위 두 자리, 분 단위 두 자리로 구성되며 오후 1시는 13시, 오후 2시는 14시, ... , 오후 10시는 22시로 표현된다. N은 50이하의 자연수이다.

출력

첫째 줄에 세혁이와 근영이가 함께할 수 있는 가장 긴 시간을 분 단위로 출력한다. 만약 함께할 수 있는 시간이 없다면 첫째 줄에 0을 출력한다.

예제 입력 1

3
1030 1300
1900 2110
1230 1650

예제 출력 1

110

 

---

 

📌 풀이

import sys
input = sys.stdin.readline

ride = [[600, 600], [1320, 1320]]
for _ in range(int(input())):
    x, y = input().split()
    x = int(x[:2]) * 60 + int(x[2:]) - 10
    y = int(y[:2]) * 60 + int(y[2:]) + 10
    ride.append([x, y])
ride.sort()

rest = 0
last = 600

for run, stop in ride:
    rest = max(rest, run - last)
    last = max(last, stop)

print(rest)

 

시각 표현 변환

10시 30분은 1030, 21시 10분은 2110 이런 식으로 입력이 들어오고, 가장 긴 휴식시간을 찾기 위해서는 시각끼리 뺄셈이 필요하기 때문에 계산하기 쉽게 바꿔주는 게 좋습니다.

0시 0분을 0으로 잡고
10시 30분 → 10*60+30=630
22시 00분 → 22*60 = 1320
요런 식으로 변환하는데, 방법은 두 가지가 있습니다.

# 정직하게 계산
(int('1030') // 100) * 60 + int('1030') % 100
# 슬라이싱 이용
int('1030'[:2]) * 60 + int('1030'[2:])

저는 정직한 계산법으로 풀었는데, 풀고 나서 다른 분들 풀이 구경하다가 새로운 방법이 있어 그 방법으로 포스팅해보려고 합니다.

놀이기구 운영 전후로 10분의 준비시간이 있으므로 시작시간에서 -10, 종료시간에서 +10까지 해주면 시각 변환은 끝입니다.

 

최대 휴식시간 계산 과정

1. 일과 시작, 종료시간인 10시와 22시를 각각 [600, 600], [1320, 1320]으로 배열에 삽입합니다.
2. 놀이기구의 시작시간을 기준으로 배열을 정렬합니다.
3. rest: 최대 휴식시간 (0으로 초기화)
   last: 앞선 놀이기구 중 가장 늦게 끝나는 것의 종료시간
   run: i번째 놀이기구의 시작시간
   stop: i번째 놀이기구의 종료시간
4. run과 last를 비교합니다.
   (1) run<last: 휴식시간이 없는 것이므로 last와 stop을 비교해서 더 늦게 끝나는 놀이기구의 종료시간을 last로 업데이트합니다.
   (2) run>last: 휴식시간이 있는 것이므로 현재 최대 휴식시간인 rest와 새로운 휴식시간인 run-last를 비교해서 더 큰 값으로 rest를 업데이트합니다. last도 (1)과 같이 비교해 업데이트합니다.