[백준 20665번] 파이썬 - 독서실 거리두기

백준 20665 - 독서실 거리두기

시간 제한 1초, 메모리 제한 512MB

# 조건

• 코로나 바이러스로 사회적 거리두기가 한창이다.
• 하지만 이러한 시국 이전에도 거리두기가 잘 지켜지던 곳이 있었으니... 바로 독서실이다.
• 독서실에서 관리자로 근무 중이던 민규는 놀라운 사실을 발견했다. 사람들은 항상 서로 더 멀리 앉으려고 노력한다는 것이었다.
• 민규는 이러한 사실을 관찰하여 잘 정리해보았다.
  1. 사람들은 가장 가까이에 앉아있는 사람이 가장 먼 자리를 선호한다. 만약 독서실을 이용하는 사람이 없다면 좌석번호 1번 자리를 가장 선호한다.
  2. 1번 규칙으로 비교할 수 없다면, 가장 먼 좌석들 중에서 좌석 번호가 가장 작은 자리를 선호한다.
• 독서실 관리자로 오래 근무한 민규에게는 선호하는 좌석이 있다. 하지만 민규는 매우 소심하기 때문에, 사람들이 본인 때문에 이용하고자하는 자리를 이용하지 못하는 일은 피하고 싶다.
• 민규가 근무하는 독서실은 09:00 부터 21:00 까지 운영되며, 철저히 예약제로 운영되기 때문에 민규는 사람들이 언제부터 언제까지 독서실을 이용하는지 알 수 있다.
• 이러한 정보를 토대로, 민규는 자신이 선호하는 자리를 얼마나 이용할 수 있는지 계산해보고자 한다.

입력

• 첫 번째 줄에 독서실 좌석의 개수 N, 독서실 예약자 수 T, 민규가 좋아하는 좌석 번호 P 가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100, 1 ≤ T ≤ 500, 1 ≤ P ≤ N)
• 다음 T 개의 줄에는 독서실 입실 시간, 독서실 퇴실 시간이 HHMM HHMM 형태로 입력된다.(0900 ≤ HHMM ≤ 2100, 0910 0900와 같이 퇴실 시간이 입실 시간보다 빠른 경우는 없다)

출력

• 민규가 선호하는 좌석을 이용할 수 있는 시간이 총 몇분인지 출력하시오.

# 제한

• 독서실의 모든 좌석은 비어있는 상태로 시작한다.
• 독서실 예약이 같은 시각에 시작된다면 짧은 이용시간을 가진 사람을 먼저 앉힌다.
• 독서실 예약 리스트에 있는 예약자들이 좌석이 없어서 못 앉는 상태는 존재하지 않는다.
• 민규는 선호하는 좌석을 얼마나 이용할 수 있는지 계산하고 싶어하는 것이기 때문에 예약인원들이 자리를 이용하는 것에 영향을 주지 않는다.

# 접근 방법

• 브루트 포스로 풀이해주었다.
• 우선 예약자를 입력 받은 후 시작 시간이 빠른 순, 퇴실 시간이 빠른 순으로 정렬을 해주고 기록해주었다.
• 첫 예약자를 info[1] => 1번 자리에 기록을 해주고 last => 마지막 이용자의 퇴실 시간을 기록해준다.
• 모든 사람을 순회하며 아래 로직으로 탐색해준다.
  • 만약 last에 기록된 시간이 현재 예약자의 입실시간 보다 느리다면 => 자리에 사람이 있다면 temp에 넣어준다.
  • maxDist, minIdx = 1로 설정해준 후 모든 자리에서 탐색을 진행한다.
  • temp => 사람이 앉아 있는 자리의 값과, 현재 탐색중인 자리의 값의 차 => 사람과의 거리를 구하여 maxDist와 비교해주고, minIdx를 갱신해준다.
  • 모든 탐색이 종료 된 후 last에는 퇴실 시간을, info에는 자리 이용자의 [입실, 퇴실] 시간을 기록해준다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

N, T, P = map(int, input().split())
times = []
for _ in range(T):
    start, end = map(str, input().strip().split())
    times.append([int(start), int(end)])

times.sort(key = lambda x:(x[0], x[1]))

last = [0] * (N+1)
info = [[] for _ in range(N+1)]

info[1].append(times[0])
last[1] = times[0][1]

for t in range(1, T):
    start, end = times[t]
    temp = []
    for i in range(1, N+1):
        if start < last[i]:
            temp.append(i)

    maxDist = 0
    minIdx = 1
    for j in range(1, N+1):
        v = 101
        for k in temp:
            v = min(abs(j-k), v)
        if v == 0:
            continue
        if v > maxDist:
            maxDist = v
            minIdx = j

    last[minIdx] = end
    info[minIdx].append([start, end])

result = 720
for i in range(len(info[P])):
    s, e = info[P][i]
    si, sj, ei, ej = s//100, s%100, e//100, e%100
    if ej - sj < 0:
        val = (ei - si - 1) * 60 + (60 - (sj - ej))
    else:
        val = (ei - si) * 60 + (ej - sj)
    result -= val
print(result)