[BOJ][Python] 백준 12764번: 싸지방에 간 준하

1일 1PS 66일차!

📚 문제

---

골드 3 싸지방에 간 준하

💡 풀이 과정

---

• 우선순위큐를 사용하는 문제입니다.
• 처음 시작시간을 기준으로 먼저 정렬을 진행한다. 이는 시간 흐름대로 컴퓨터 사용을 결정할 것이므로 당연합니다.
  • 첫 번째 사람이 들어오면 끝나는 시간을 큐에 삽입합니다.
  • 두 번재 사람부터는 최소힙에서 peek 값이 자신의 시작시간보다 크다면 새로운 컴퓨터를 사용합니다.
    • 만약 작다면 해당 번째 컴퓨터를 이어 사용하며 역시 끝 시간을 삽입합니다.

• 컴퓨터 사용 횟수는 최소힙에 (끝나는 시간, 컴퓨터 번호) 를 함께 기록해 관리합니다.

• 처음에 이렇게 문제를 풀었지만 한 가지 조건이 더 남아있었습니다.
• “비어있는 컴퓨터 자리 중에서 가장 작은 번호 사용”
  • 즉, 컴퓨터 자리도 정렬이 필요하며 이는 새로운 최소힙으로 구현할 수 있습니다.
  • 두 번째 사람부터 peek 값이 자신의 시작시간보다 작다면 모두 pop 해내고 해당 자리들은 비어있으므로 자리 번호를 새로운 최소힙에 삽입합니다.
    • 비어있는 자리를 모두 파악했으면 그 중 가장 작은 번호의 컴퓨터를 사용합니다.
  • 이후부터는 peek 값에 따라 다시 비어있는 자리들을 추가하고 그중 작은 것을 선택하거나,
  • peek 값이 크다면 이미 비워진 자리가 있는 지 확인하는 로직을 추가합니다.

📌포인트

---

• IndexException
  • while 같은 반복문을 사용할 때 pop 을 내부 로직으로 가지고 있다면 pop 할 요소가 있는 지 확인하는 조건문이 필요할 수 있습니다.

💻 코드

---

import sys
import heapq

N = int(sys.stdin.readline())

computers = []
seats = []
min_time = []
count = []

for _ in range(N):
    computers.append(list(map(int, sys.stdin.readline().split())))

computers.sort(key=lambda x:x[0])
for start, end in computers:
    if not min_time:
        heapq.heappush(min_time, (end, len(count)))
        count.append(1)
    else:
        if start > min_time[0][0]:
            while min_time and start > min_time[0][0]:
                time, index = heapq.heappop(min_time)
                heapq.heappush(seats, index)

            min_index = heapq.heappop(seats)
            heapq.heappush(min_time, (end,min_index))
            count[min_index] += 1

        else:
            if seats:
                min_index = heapq.heappop(seats)
                heapq.heappush(min_time, min_index)
                count[min_index] += 1
            else:
                heapq.heappush(min_time, (end,len(count)))
                count.append(1)



print(len(count))
print(" ".join(map(str, count)))