99클럽 코테 스터디 19일차 TIL + 우선순위큐

백준 1374번 강의실

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	8489	3843	3048	46.294%

문제

N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.

물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.

[입력]

첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이고, 시작 시간은 종료 시간보다 작다.

[출력]

첫째 줄에 필요한 최소 강의실 개수를 출력한다.

---

문제 해석하기

모든 강의를 시작 시간을 기준으로 정렬해서 시간 순서대로 처리될 수 있도록 한다. ⇒ 까지만 생각함..
뒷 부분들의 처리를 어떻게 해야할지 몰라서 찾아봤는데 ‘우선순위 큐 즉 힙’ Heap 을 사용하는 방법을 알 수 있었다.

• 강의의 개수를 입력받고, 다음 입력줄에서 강의 번호, 시작시간, 종료시간을 리스트로 입력받는다.
• 해당 강의의 시작시간을 바탕으로 오름차순으로 정렬하여 시간 순서대로 처리할 수 있도록 한다.
• 우선순위큐를 사용해서 현재 사용중인 강의실의 종료시간을 알 수 있도록 한다.
  • 강의실 종료 시간 중에서 가장 빨리 끝나는 시간이 필요해서 최소 힙(min-heap)을 사용해서 확인한다
• 강의를 순서대로 처리하면서, 우선순위 큐에 있는 강의실들의 종료 시간과 비교한다.
• 현재 강의의 시작 시간이 우선순위 큐의 최솟값(가장 이른 종료 시간)보다 크거나 같으면, 해당 강의실을 비워 사용할 수 있도록 한다.
  • 이 경우 우선순위 큐에서 최소 종료 시간을 제거한다
  • 그렇지 않으면 새로운 강의실이 필요하므로 강의실을 추가한다.
  • 현재 강의의 종료 시간을 우선순위 큐에 추가

import sys
import heapq

input = sys.stdin.readline

# 강의 수 입력
N = int(input())

# 강의 정보 입력 및 시작 시간 기준 정렬
lectures = [list(map(int, input().split())) for _ in range(N)]
lectures.sort(key=lambda x: x[1])  # 시작 시간을 기준으로 정렬

# 최소 힙 생성
min_heap = []
max_rooms = 0

# 강의 순회
for lecture in lectures:
    start_time = lecture[1]
    end_time = lecture[2]

    while min_heap and min_heap[0] <= start_time:
        heapq.heappop(min_heap)
    
    heapq.heappush(min_heap, end_time)
    
    max_rooms = max(max_rooms, len(min_heap))

# 결과 출력
print(max_rooms)

---

우선순위큐란?

우선순위 큐(Priority Queue)는 일반적인 큐(Queue)와 달리 데이터의 우선순위에 따라 정렬되어 처리되는 자료구조이다. 우선순위가 높은 데이터가 먼저 나온다

1) 우선순위큐

• 우선순위에 따라 데이터가 삽입 및 제거된다
• 최소 힙(Min-Heap) 또는 최대 힙(Max-Heap)을 이용해 구현된다
  • 최소 힙: 우선순위가 낮은 값이 먼저 나옴
  • 최대 힙: 우선순위가 높은 값이 먼저 나옴
• Python에서는 heapq 모듈을 사용하여 최소 힙으로 구현할 수 있다

import heapq

min_heap = []
heapq.heappush(min_heap, 5)  # 5 삽입 => heappush를 이용함
heapq.heappush(min_heap, 2)  # 2 삽입
heapq.heappush(min_heap, 8)  # 8 삽입
print(heapq.heappop(min_heap))  # 2 제거 (최소값 출력)
# => heappop을 이용해서 제거를 할 수 있도록 함

2) 람다 함수

• 람다 함수(Lambda Function)는 Python에서 사용하는 익명 함수로, 이름 없이 짧은 코드로 함수를 정의할 때 사용된다.
• 일반적으로 한 줄로 작성되는 간단한 함수를 만들 때 사용한다
• 보통 람다 함수는 정렬에서 많이 활용되며, sort() 또는 sorted()의 key 옵션에서 자주 사용된다.

data = [(1, 3), (2, 2), (4, 1)]
data.sort(key=lambda x: x[1])  # 두 번째 요소를 기준으로 정렬
print(data)  # 출력: [(4, 1), (2, 2), (1, 3)]

---

오늘의 회고

우선순위큐라는 것을 새롭게 사용해보면서 문제를 쉽게 해결할 수 있는 방법을 또 하나 얻어갈 수 있었다. 람다 함수에 대해서도 알고는 있었지만 많이 사용해보지는 않았는데, 이 문제를 통해서 정렬에서 자주 사용된다는 점을 더 이해할 수 있었다.