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

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

 

코드

n, t, p = map(int, input().split())
time = []
for _ in range(t):
    s, e = map(int, input().split())
    s = s//100*60+s % 100
    e = e//100*60+e % 100
    time.append((s, e))
time.sort()
ans = 60*12


def find_seat(arr):  # 앉을 자리 선택
    if not arr:  # 아무도 없는 경우
        return 1
    candidate = []  # 앉을 자리 후보
    if arr[0][0] != 1:  # 1번 좌석
        candidate.append((arr[0][0]-1, 1))
    if arr[-1][0] != n:  # N번 좌석
        candidate.append((n-arr[-1][0], n))
    for i in range(1, len(arr)):    # 지금 앉아있는 사람들의 사이 좌석
        candidate.append(((arr[i][0]-arr[i-1][0])//2,
                         (arr[i][0]+arr[i-1][0])//2))
    # 조건에 맞는 자리 1자리만 리턴
    return sorted(candidate, key=lambda x: (-x[0], x[1]))[0][1]


used = []
for s, e in time:
    new_used = []   # 현재(시간: s) 사용중인 좌석
    for u in used:  # 퇴실한 좌석 걸러내기
        if u[1] > s:
            new_used.append(u)
    res = find_seat(new_used)   # 좌석 선택
    if res == p:    # 민규가 좋아하는 자리에 누가 앉음
        ans -= (e-s)
    new_used.append((res, e))
    used = sorted(new_used)
print(ans)

 

1. 사용자들의 입/퇴실 시간이 기록된 리스트 time을 입실 시간을 기준으로 정렬한다.

2. 정렬된 순서대로 find_seat () 함수를 이용하여 자리를 하나씩 배정한다. 만약 배정된 자리가 민규가 앉고 싶어하는 자리라면 ans에서 현재 이용자가 이용할 시간만큼 빼준다.

 

find_seat()

이미 사람들이 앉아있는 좌석 번호와 퇴실 시간을 기록한 배열 arr을 파라미터로 받아서 지금 앉는 사람은 어디에 앉아야할지 알려주는 함수이다.

- 만약 arr이 비었다면 앉아있는 사람이 없다는 말이므로 1을 리턴한다.

- (가장 가까운 사람까지 거리, 앉을 자리 후보) 튜플을 저장하는 배열 candidate를 생성한다. 만약 1번과 N번 자리가 사용 중이 아니라면 candidate에 넣어준다. 그리고 사람과 사람 사이에 앉게되는 경우는 둘 사이의 가운데에 앉으면 되므로 (arr[i][0]-arr[i-1][0])//2,(arr[i][0]+arr[i-1][0])//2)를 넣어준다. 이렇게 구한 candidate 중 가까운 사람과의 거리가 가장 먼 자리를 리턴하면 되므로 가장 가까운 사람과의 거리를 내림차순 정렬하여 0번째 원소의 자리를 리턴한다.