BOJ-11000 강의실 배정 Swift

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

내가 푼 풀이

- 주어진 수업들의 시간이 겹치지 않으면 같은 강의실을 사용한다.

- 수업들의 시작시간을 오름차순으로 정렬하고, 끝나는 시간을 배열에 넣어서 시작시간보다 같거나 작으면 같은 강의실을 이용하는 방법으로

코드를 짰는데, 80퍼에서 자꾸 시간초과가 떴다.

- 수업의 갯수가 최대 20만이고, 최악의 상황으로 모든 수업이 겹친다면, 강의실도 20만 개이므로 위 같은 코드는 O(n^2)으로 시간초과가 났다.

- 위 같은 조건으로 탐색하지만, 시간초과가 나서 더 빠른방법인 우선순위큐를 이용해서 풀었다.

- 우선순위큐의 가장 앞원소는 수업의 종료시간이 가장 빠른순으로 한다.

 

 

• 수업들을 입력받아 시작시간 기준으로 정렬한다.
• 첫번째 수업의 종료시간을 우선순위 큐에 넣는다. 우선순위큐에는 수업의 종료시간이 들어가고 가장 빨리 끝나는 순으로 정렬된다.
• 다음 수업과 우선순위큐의 첫 번째 원소랑 비교한다.
• 수업의 시작시간이 첫번째 원소랑 같거나 크다면, 같은 강의실을 이용할 수 있으므로, 다음 수업의 종료시간으로 갱신한다. ( pop -> push)
• 수업의 시작시간이 첫번째 원소보다 크다면, 다른 강의실을 이용해야 하므로 우선순위큐에 해당 수업의 종료시간을 넣는다. (push)
• 모든 수업을 위 조건과 비교한 후 큐의 크기를 출력한다.

 

 

알고리즘도 맞고 예제도 맞고 하는데 자꾸 틀렸다고 나왔는데,

Swift는 힙과 우선순위 큐를 직접 구현해야 하다 보니, 사소하게 순서를 잘못 적어서 제 기능을 제대로 못하는 경우였다.

우선순위큐는 힙을 바탕으로 구현하는데, 힙은 배열로 구현하고 힙의 특성 중 가장 중요한 게 배열의 sort 기능이다.

최소힙, 최대힙이 정해질때 배열의 sort기능을 사용하는데 (T, T) -> Bool에서 인자의 순서가 중요할 줄 몰랐는데,

아무래도 { $0 < $1 }인 클로저의 첫번째 두 번째 인자를 사용하면서 순서가 중요한 듯했다.

나중에 sort 관련해서 정리해 둬야겠다. 

 

 

import Foundation

// 힙 구현
struct Heap<T: Comparable> {
    private var elements: [T] = []
    private let sortFunction: (T, T) -> Bool
    
    var isEmpty: Bool {
        return self.elements.count == 1
    }
    
    var peek: T? {
        if self.isEmpty { return nil}
        return self.elements[1]
    }
    
    var count: Int {
        return self.elements.count - 1
    }
    
    init(elements: [T] = [], sortFuntion: @escaping (T,T) -> Bool) {
        if !elements.isEmpty {
            self.elements = [elements.first!] + elements
        } else {
            self.elements = elements
        }
        self.sortFunction = sortFuntion
        if elements.count > 1 {
            self.buildHeap()
        }
    }
    
    func leftChild(of index: Int) -> Int {
        return index * 2
    }
    func rightChild(of index: Int) -> Int {
        return index * 2 + 1
    }
    func parent(of index: Int) -> Int {
        return index / 2
    }
    
    mutating func swimUp(from index: Int) {
        var index = index
        while index != 1 && self.sortFunction(self.elements[index], self.elements[self.parent(of: index)]) {
            self.elements.swapAt(index, self.parent(of: index))
            index = self.parent(of: index)
        }
    }
    
    mutating func insert(node: T) {
        if self.elements.isEmpty {
            self.elements.append(node)
            return
        }
        self.elements.append(node)
        self.swimUp(from: self.elements.endIndex - 1)
    }
    
    mutating func diveDown(from index: Int) {
        var higherPriority = index
        let leftIndex = self.leftChild(of: index)
        let rightIndex = self.rightChild(of: index)
        
        if leftIndex < self.elements.endIndex && self.sortFunction(self.elements[leftIndex], self.elements[higherPriority]) {
            higherPriority = leftIndex
        }
        
        if rightIndex < self.elements.endIndex && self.sortFunction(self.elements[rightIndex], self.elements[higherPriority]) {
            higherPriority = rightIndex
        }
        
        if higherPriority != index {
            self.elements.swapAt(higherPriority, index)
            self.diveDown(from: higherPriority)
        }
        
    }
    
    mutating func buildHeap() {
        for index in (1...(self.elements.count / 2)).reversed() {
            self.diveDown(from: index)
        }
    }
    
    mutating func remove() -> T? {
        if self.elements.isEmpty { return nil }
        self.elements.swapAt(1, elements.endIndex - 1)
        let deleted = elements.removeLast()
        self.diveDown(from: 1)
        
        return deleted
    }
    
}

// 우선순위 큐 구현
struct PriorityQueue<T: Comparable> {
    var heap: Heap<T>
    
    init(_ elements: [T] = [], _ sort: @escaping (T,T) -> Bool) {
        heap = Heap(elements: elements, sortFuntion: sort)
    }
    
    var count: Int {
        return heap.count
    }
    
    var isEmpty: Bool {
        return heap.isEmpty
    }
    
    func top() -> T? {
        return heap.peek
    }
    
    mutating func clear() {
        while !heap.isEmpty {
            heap.remove()
        }
    }
    
    mutating func pop() -> T? {
        return heap.remove()
    }
    
    mutating func push(_ element: T) {
        heap.insert(node: element)
    }
}


let count = Int(readLine()!)!
var classArr = [[Int]]()

// 수업들 입력받기
for i in 0..<count {
    let inputs = readLine()!.split(separator: " ").map{ Int($0)! }
    classArr.append(inputs)
}

// 수업의 시작시간 기준으로 정렬
// 시작시간이 같다면 종료시간이 빠른순으로 정렬
var sortedArr = classArr.sorted{
    if $0[0] == $1[0] {
        return $0[1] < $1[1] } else {
        return $0[0] < $1[0]
    }}

// 우선순위큐에 첫번째 수업의 종료시간을 넣는다.
var pq = PriorityQueue([Int]() , { $0 < $1 })
pq.push(0)
pq.push(sortedArr[0][1])

// 오름차순으로 정렬된 수업배열을 우선순위큐의 첫번째 원소와 비교
// 우선순위의 첫번째 원소와 수업의 시작시간을 비교했을때,
// 원소값 <= 수업시작시간: 같은 강의실 사용한다. 원소값 pop 후 수업의 종료시간 push
// 원소값 > 수업시작시간: 수업시간이 겹치므로 다른 강의실 사용한다. 수업의 종료시간 push
for i in 1..<sortedArr.count {
    let s = sortedArr[i][0]
    let t = sortedArr[i][1]
    
    pq.push(t)
    if pq.top()! <= s {
        pq.pop()
    }

}

print(pq.count)