[파이썬][백준 19598][💛골드 5] (그리디, 우선순위큐)

🧞‍♂️ 난이도

💛 골드 5

🧞‍♂️ 문제

최소 회의실 개수

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

강의실 배정 (똑같은 문제)

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

🧞‍♂️ 유형

그리디, 우선순위큐

🧞‍♂️ 내 풀이

이 문제는 우선순위큐를 이용하여 그리디하게 풀면 되는 문제이다.

잘 생각해보면, 진행되고있는 강의 중의 가장 먼저 시작한 강의의 끝나는 시각 이랑 다음에 진행될 강의의 시작 시간 만 비교하면 된다.

이걸 이용해서 알고리즘을 만들면 된다.

1. 일단 강의 정보를 정렬시킨다.
2. 강의 정보들을 하나씩 우선순위큐에 넣을건데. 끝나는 시각만 넣을거다
3. 우선순위큐에 들어있는 가장 먼저 시작하는 정보(queue[0]) 와 새롭게 들어올 강의 정보의 시작시간을 비교한다
4. 만약에 새롭게 들어갈 강의 정보의 시작 시간이 크거나 같으면 우선순위큐에서 pop을 한다.
5. 그리고 새롭게 들어갈 강의 정보의 끝나는 시각을 우선순위큐에 넣어준다

그럼 최종적으로 큐에 남아있는 강의의 개수는 강의실 개수가 된다. ***

🧞‍♂️ 파이썬 풀이

import sys, heapq
input = sys.stdin.readline

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

print(len(h))

🧞‍♂️ 다른 사람 풀이

다른 사람 제출 코드 중에 신기한걸 발견했는데 마음에 들어서 기록해둬야겠다 로직은 다음과 같다

1. 회의 시작 시간, 회의 끝나는 시각을 아예 다른 데이터로 분리를 한다
2. 시작 시간은 1, 끝나는 시간은 -1 로 표시한다
3. 정렬한다.
4. 그럼 문제에서 주어진 예제는 0 40 15 30 5 10

정렬하면

(0, 1), (5, 1), (10, -1), (15, 1), (30, -1), (40, 1)

이렇게 되는거다

1. 뒤에 있는 1/-1 를 차례대로 더하면서 최댓값을 구한다.
   • 첫 데이터, 두번째 데이터 더했을때 (2) 가 최댓값이다

🧞‍♂️ 스위프트 풀이

import Foundation

let N  = Int(readLine()!)!
var data: [(Int, Int)] = []

for _ in 0..<N {
    let input = readLine()!.split(separator: " ").compactMap { Int($0) }
    
    data.append((input[0], 1))
    data.append((input[1], -1))
}

data.sort(by: <)

var sum = 0, answer = 0

for (_, type) in data {
    sum += type
    answer = max(answer, sum)
}

print(answer)

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기