[BOJ] Python, Ruby 백준 최소 회의실 개수 (19598)

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

 

최소힙을 사용한 그리디 문제이다.

우선 받은 배열을 정렬한다

이후, 배열을 순회하며 힙 내에 도착지에 최소값이 다음 start 값보다 작다면 회의실을 연결되서 쓸 수 있다는 뜻이므로, 힙에서 나온 도착지의 최소값을 pop 해준다.

 

다음 최소힙에 무조건 값을 넣어준다. (회의실 무조건 배정)

 

python

import sys
import heapq
input = sys.stdin.readline

N = int(input())
s = sorted([list(map(int,input().split())) for _ in range(N)])
hq = []
for start, end in s:
    if hq and hq[0] <= start:
        heapq.heappop(hq)
    heapq.heappush(hq,end)

print(len(hq))

 

Ruby

require 'set'
require 'priority_queue'


N = gets.to_i
s = Array.new(N) { gets.split.map(&:to_i) }


hq = PriorityQueue.new

s.each do |start, end_time|
  if !hq.empty? && hq.min <= start
    hq.delete_min
  end
  hq.push(end_time, end_time) 
end

puts hq.length

 

회고.

간단한 코드임에도 불구하고 초반 정렬을 하지않아 값의 순차적 증가를 해주지 못해 문제가 발생했다.

유기적으로 연결되어있는 구현도 실력을 늘리고, 최소힙에 대한 이해도도 높혀야 겠다..