[백준(BOJ)] 11000 강의실 배정 - 스위프트(Swift)

[Gold V] 강의실 배정 - 11000

문제 링크

성능 요약

메모리: 76356 KB, 시간: 316 ms

분류

자료 구조, 그리디 알고리즘, 우선순위 큐, 정렬

문제 설명

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

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

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

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

입력

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

이후 N개의 줄에 S_i, T_i가 주어진다. (0 ≤ S_i < T_i ≤ 10⁹)

출력

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

 

풀이

i)

시작 시간을 기준으로 값을 정렬한 뒤, 종료 시간을 선정합니다.

그리고 종료 시간과 다음 수업 시간을 비교하여 만약 수업 시간이 먼저 시작하면 큐에 값을 추가하고, 만약 종료 이후에 수업이 시작한다면 선정한 종료 시간을 큐에서 제거하고, 새로 시작하는 수업의 종료 시간을 큐에 삽입하였습니다.

let n = Int(readLine()!)!
var (queue, st) = ([Int](), [(Int, Int)]())

for _ in 0..<n {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    st.append((input[0], input[1]))
}
st.sort(by: (<))    // 시작 시간을 기준으로 오름차순 정렬
queue.append(st[0].1)   // 첫 번째 종료 시간 추가

for i in 0..<n-1 {
    if queue.first! > st[i+1].0 {   // 첫 번째 종료 시간이 다음 시작 시간보다 늦게 끝나면 교실 생성 -> 큐에 추가
        queue.append(st[i+1].1)
    } else {    // 종료 뒤 다음 수업 시작 가능 시 -> 해당 종료 시간 제거하고 다음 종료 시간 추가
        queue.removeFirst()
        queue.append(st[i+1].1)
    }
}

print(queue.count)

→ 틀렸습니다.

 

종료 시간이 큐에 들어올 때, 더 종료가 빠른 값이 뒤에 있는 경우가 생겨 틀렸습니다.

종료가 더 먼저 되는 것이 있다면 먼저 없애줘야하는데, 이러한 경우를 고려하지 않았습니다. 

 

ii)

따라서 큐에 값이 들어갈 때마다 sort를 사용하여 큐를 정렬해주었습니다.

let n = Int(readLine()!)!
var (queue, st) = ([Int](), [(Int, Int)]())

for _ in 0..<n {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    st.append((input[0], input[1]))
}
st.sort(by: (<))    // 시작 시간을 기준으로 오름차순 정렬
queue.append(st[0].1)   // 첫 번째 종료 시간 추가

for i in 0..<n-1 {
    if queue.first! > st[i+1].0 {   // 첫 번째 종료 시간이 다음 시작 시간보다 늦게 끝나면 교실 생성 -> 큐에 추가
        queue.append(st[i+1].1)
    } else {    // 종료 뒤 다음 수업 시작 가능 시 -> 해당 종료 시간 제거하고 다음 종료 시간 추가
        queue.removeFirst()
        queue.append(st[i+1].1)
    }
    queue.sort()    // 종료가 빠른 순서대로 정렬
}

print(queue.count)

→ 시간 초과

 

sort 함수의 시간 복잡도는 O(n log n)인데, 이를 for문과 함께 사용하여 해당 식의 시간 복잡도가 O(n^2 log n)이 되었기 때문에 시간이 초과되었습니다. 

 

iii)

결국 해당 문제는 우선순위 큐를 사용하여 시작 시간과 종료 시간을 조정해야했습니다.

 

우선순위 큐는 종료 시간을 기준으로 정렬되도록 하고,

큐의 가장 첫 번째 값과 시작 시간을 비교하여 시작이 가능하면 해당 값을 큐에서 제거해줍니다.

그리고 종료 시간을 추가해준 뒤, 큐의 길이를 계산해줍니다.

struct PriorityQueue<Element: Comparable> { // 우선순위 큐
    private var elements: [Element] = []
    
    var isEmpty: Bool {
        return elements.isEmpty
    }
    
    var count: Int {
        return elements.count
    }
    
    mutating func push(_ element: Element) {
        elements.append(element)
        siftUp()
    }
    
    mutating func pop() -> Element? {
        if elements.isEmpty {
            return nil
        }
        if elements.count == 1 {
            return elements.removeFirst()
        }
        
        let first = elements[0]
        elements[0] = elements.removeLast()
        siftDown()
        
        return first
    }
    
    func peek() -> Element? {
        return elements.first
    }
    
    private mutating func siftUp() {
        var childIndex = elements.count - 1
        while childIndex > 0 {
            let parentIndex = (childIndex - 1) / 2
            if elements[childIndex] >= elements[parentIndex] {
                break
            }
            elements.swapAt(childIndex, parentIndex)
            childIndex = parentIndex
        }
    }
    
    private mutating func siftDown() {
        var parentIndex = 0
        while true {
            let leftChildIndex = 2 * parentIndex + 1
            let rightChildIndex = 2 * parentIndex + 2
            var minIndex = parentIndex
            
            if leftChildIndex < elements.count && elements[leftChildIndex] < elements[minIndex] {
                minIndex = leftChildIndex
            }
            if rightChildIndex < elements.count && elements[rightChildIndex] < elements[minIndex] {
                minIndex = rightChildIndex
            }
            
            if minIndex == parentIndex {
                break
            }
            
            elements.swapAt(parentIndex, minIndex)
            parentIndex = minIndex
        }
    }
}

let n = Int(readLine()!)!
var (queue, st) = (PriorityQueue<Int>(), [(Int, Int)]())

for _ in 0..<n {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    st.append((input[0], input[1]))
}
st.sort(by: (<))    // 시작 시간을 기준으로 오름차순 정렬

for lesson in st {
    let startTime = lesson.0    // 시작 시간
    let endTime = lesson.1  // 종료 시간
    
    if let earlistEndTime = queue.peek(), earlistEndTime <= startTime {
        queue.pop()
    }
    queue.push(endTime)
}
print(queue.count)

 

스위프트의 단점은 이러한 큐가 구현되어 있지 않기 때문에 직접 구현해주어야 한다는 점입니다. 아직은 외우지 않았지만 언젠가 외워야,,겠지?