백준 11000 강의실 배정

출처: www.acmicpc.net/problem/11000

분류: priority queue, greedy

---

접근방식

문제를 똑바로 안 읽어서 좀 헤맸던 문제입니다..

문제를 잘 이해해야 하는데요, 강의실에 수업을 배정하는 것이 아니라, 강의를 소화할 수 있게 강의실을 몇 개나 만들어야 하는지 찾는 문제입니다.

따라서 수업을 시작시간을 기준으로 정렬해두고,

생성된 강의실들 중에서 가장 빨리 끝나는 강의실과 수업의 시작시간을 비교해서 시작이 가능하다면 그 강의실에 배정합니다.

우선순위 큐에서 하나 꺼내고 해당 강의실을 집어넣으면 같은 의미가 됩니다!

이렇게 진행하고 결과적으로 우선순위 큐에 남아있는 원소의 개수가 강의실의 개수가 됩니다.

 

간단하게만 대략적인 그림으로 살펴보면,

아래 그림과 같이 강의실 3개가 이미 배정되어 있고, 우선순위 큐에는 각 강의실이 끝나는 시간이 들어있습니다.

이때 새로운 강의(4~6) 을 추가하려고 한다면,

우선순위 큐의 탑인 4와 새 강의의 시작시간 4를 비교해서 배정 가능한지 확인합니다.

배정 가능하다면 우선순위 큐의 탑인 4를 빼내고 새 강의의 종료시간인 6을 넣어서

우선순위 큐에는 [ 5, 6, 6 ] 이 남게 되겠죠!! 

해결방법

public struct Heap<T> {
    
    private var nodes = [T]()
    
    private var orderCriteria: (T, T) -> Bool
    
    public init(sort: @escaping (T, T) -> Bool) {
        // 최대 힙인지 최소 힙인지 기준을 잡는다.
        self.orderCriteria = sort
    }
    
    public init(array: [T], sort: @escaping (T, T) -> Bool) {
        self.orderCriteria = sort
        configureHeap(from: array)
    }
    
    public var count: Int {
        return nodes.count
    }
    
    public func peek() -> T? {
        return nodes.first
    }
    
    public mutating func insert(_ value: T) {
        nodes.append(value)
        shiftUp(nodes.count - 1)
    }
    
    public mutating func remove() -> T? {
        guard !nodes.isEmpty else { return nil }
        
        if nodes.count == 1 {
            return nodes.removeLast()
        } else {
            let value = nodes[0]
            nodes[0] = nodes.removeLast()
            shiftDown(0)
            return value
        }
    }
    
    public mutating func remove(at index: Int) -> T? {
        guard index < nodes.count else { return nil }
        
        let lastIndex = nodes.count-1
        if index != lastIndex {
            nodes.swapAt(index, lastIndex)
            shiftDown(from: index, until: lastIndex)
            shiftUp(index)
        }
        
        return nodes.removeLast()
    }
    
    // 변수를 직접 변경해야 하기 때문에 mutating 을 사용한다.
    private mutating func configureHeap(from array: [T]) {
        nodes = array
        
        /**
         * 힙 트리에서 n/2 - 1 은 하나 위 층위가 된다.
         * shiftDown을 하면서 자리를 잡을 것이기 때문에
         * 마지막 leaf 노드들은 할 필요가 없다.
         */
        for i in stride(from: nodes.count/2 - 1, through: 0, by: -1) {
            shiftDown(i)
        }
    }
    
    private func parentIndex(ofIndex i: Int) -> Int {
        return (i - 1) / 2
    }
    
    private func leftChildIndex(ofIndex i: Int) -> Int {
        return 2*i + 1
    }
    
    private func rightChildIndex(ofIndex i: Int) -> Int {
        return 2*i + 2
    }
    
    /**
     * shiftUp은 자신과 부모를 비교해 바꿔준다.
     */
    private mutating func shiftUp(_ index: Int) {
        var childIndex = index
        let child = nodes[childIndex] // 처음에 노드를 저장해두고 인덱스를 구한 후 바꿔준다.
        var parentIndex = self.parentIndex(ofIndex: index)
        
        while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) {
            nodes[childIndex] = nodes[parentIndex]
            childIndex = parentIndex
            parentIndex = self.parentIndex(ofIndex: childIndex)
        }
        
        nodes[childIndex] = child
    }
    
    /**
     * shiftDown은 left, right 자식 중 적합한 녀석이 있으면 바꾸면서 바닥까지 내려간다.
     */
    private mutating func shiftDown(from index: Int, until endIndex: Int) {
        let leftChildIndex = self.leftChildIndex(ofIndex: index)
        let rightChildIndex = leftChildIndex + 1
        
        var first = index
        if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) {
            first = leftChildIndex
        }
        if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) {
            first = rightChildIndex
        }
        if first == index { return }
        
        nodes.swapAt(index, first)
        shiftDown(from: first, until: endIndex)
    }
    
    private mutating func shiftDown(_ index: Int) {
        shiftDown(from: index, until: nodes.count)
    }
    
}

typealias Lecture = (s: Int, e: Int)
var lectures = [Lecture]()

for _ in 0..<Int(readLine()!)! {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    lectures.append((input[0], input[1]))
}

lectures.sort(by: { $0.s < $1.s })
var heap = Heap<Lecture>(sort: { $0.e - $0.s < $1.e - $0.s })
heap.insert(lectures[0])

for i in 1..<lectures.count {
    let lec = lectures[i]
    if lec.s >= heap.peek()!.e {
        heap.remove()
    }
    heap.insert(lec)
}

print(heap.count)

 

배운점

화이팅