[백준/python] 20665번 독서실 거리두기

1. 문제

 

독서실에서 원하는 자리를 이용 가능한 시간을 구하는 문제다.

1, 2번 규칙에 따라 새로 온 사람이 이용하는 좌석을 파악해 문제를 해결해야 한다.

 

2. 풀이

<아이디어>
1. 0900 ~ 2100 이라는 숫자로 나오지만 이걸 분 형태로 바꿔주어야 계산이 편함 (아니면 9시 ~ 10시가 100분이 됨..!)
2. 사람들이 선호하는 좌석을 구하는 함수 만들기
3. heapq를 사용하여 새로운 사람이 오면 추가하고 visited를 True로 바꾸어주기
4. 정답은 720에서 시작해서 자리를 사용할 수 없는 시간 만큼 빼기

<좌석 번호 구하기 함수>
1. max_dist, best_seat 변수 초기화
2. 1부터 n+1까지 돌려서 각각 좌석 번호에 대하여, 이미 방문하지 않은 경우에만 실행
3. left_dist, right_dist를 무한대로 초기화하고 왼쪽 오른쪽으로 이동함
4. 가장 가까운 점유된 좌석(visited = True)을 만났을 때 거리를 갱신함
5. 해당 좌석의 거리를 left_dist와 right_dist 중 최솟값으로 초기화함
6. 만약 거리가 max_dist 보다 클 경우 max_dist와 best_seat 갱신 (문제의 1번 규칙)
7. 또는 거리가 max_dist와 같고 i가 best_seat 보다 작다면 best_seat을 i로 초기화 (문제의 2번 규칙)

3. 코드

import heapq

n, t, p = map(int, input().split())
times = [tuple(map(lambda x: int(x[:2]) * 60 + int(x[2:]), input().split())) for _ in range(t)]

def get_best_seat():
    max_dist = 0
    best_seat = 1
    for i in range(1, n + 1):
        if visited[i]:
            continue
        left_dist = right_dist = float('inf')

        for j in range(i - 1, 0, -1):
            if visited[j]:
                left_dist = i - j
                break
        
        for j in range(i + 1, n + 1):
            if visited[j]:
                right_dist = j - i
                break
        
        dist = min(left_dist, right_dist)
        if dist > max_dist:
            max_dist = dist
            best_seat = i
        elif dist == max_dist and i < best_seat:
            best_seat = i
    
    return best_seat

times.sort()

visited = [False] * (n + 1)

ans = 720
pq = []

for start, end in times:
    while pq and pq[0][0] <= start:
        _, seat = heapq.heappop(pq)
        visited[seat] = False

    best_seat = get_best_seat()
    if best_seat == p:
        ans -= end - start

    visited[best_seat] = True
    heapq.heappush(pq, (end, best_seat))

print(ans)

4. 느낀점

풀면서 너무 어렵고 막막했다.

처음에는 별 생각 없이 해당하는 좌석이 몇 번째로 점유되는지만을 계산해두고

해당하는 인원 이상이 오면 그 자리를 사용 불가한 것으로 계산했었으나,

인원수가 중요한게 아니라 그 자리 자체가 중요함을 나중에 깨달았다.

시간 단축을 위해 heapq를 사용하였고 자리가 점유되지 않는 시간을 더하는 것보다는

자리가 점유된 시간 만큼을 빼는게 변수도 덜 사용하고 구하기가 편했다.

 

골드4 구현 문제는 난이도가 장난 아니다.... 어려웠다.