[BOJ] 백준 11000 강의실 배정 풀이 (swift)

강의실 배정

풀이(투 포인터)

해당 문제에 우선순위 큐와 자료구조? 사실 우선순위 큐를 구현해서까지 풀어야 하나? 라는 생각을 가장 먼저 했습니다. (직접 구현할 줄 몰라서 그런것도 있고)

그래서 저는 우선순위 큐를 사용하지 않고 강의가 겹치는지 여부만 확인하고 각 회의의 시작과 종료 시간을 분리한 후 시작과 종료를 순차적으로 처리하는 방식으로 풀이를 했습니다.

let N = Int(readLine()!)!

var startTimes = [Int]()
var endTimes = [Int]()

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

// 시작 시간과 종료 시간을 각각 정렬
startTimes.sort()
endTimes.sort()

var startPointer = 0
var endPointer = 0
var currentRooms = 0
var maxRooms = 0

while startPointer < N {
    if startTimes[startPointer] < endTimes[endPointer] {
        // 새로운 강의실이 필요하므로 현재 강의실 수 증가
        currentRooms += 1
        maxRooms = max(maxRooms, currentRooms)
        startPointer += 1
    } else {
        // 기존 강의실이 비게 되므로 강의실 수 감소
        currentRooms -= 1
        endPointer += 1
    }
}

print(maxRooms)

위 풀이의 경우 startTimes 배열과 endTimes 배열을 각각 오름차순으로 정렬합니다.
startPointer와 endPointer를 각각 startTimes와 endTimes의 시작 위치에 놓고, 시작 시간이 종료 시간보다 빠르면 강의실을 추가하고 startPointer를 증가시킵니다.
반대로 종료 시간이 더 빠르면 강의실 하나가 비게 되므로 endPointer를 증가시키고 강의실 개수를 조정합니다.
이 방식을 사용하면 전체 탐색에 O(N) 시간이 소요되므로 효율적입니다.

아래의 풀이는 같이 스터디하는 동생의 풀이방법을 swift로 변경해봤습니다.

let N = Int(readLine()!)!

var startTimes = Array(repeating: 0, count: N)
var endTimes = Array(repeating: 0, count: N)

for i in 0..<N {
    let input = readLine()!.split(separator: " ").compactMap { Int($0) }
    startTimes[i] = input[0]
    endTimes[i] = input[1]
}

// 시작 시간과 종료 시간을 각각 정렬
startTimes.sort()
endTimes.sort()

var roomCount = 0
var endIndex = 0

for i in 0..<N {
    if (startTimes[i] >= endTimes[endIndex]) {
        endIndex += 1
    }
    else {
        roomCount += 1
    }
}
print(roomCount)

이것 역시 시작 시간과 종료 시간을 쪼개서 정렬시킨 뒤 시간 시간 순으로 순회하면서 강의실을 배정하는 방법입니다. 아래는 6번 정도의 트라이 흔적입니다. 48ms 걸리는 코드는 Rhyno 님의 FileIO Class 를 사용한 코드 입니다. 입력만 다르게 받을 뿐 코드는 똑같습니다.

읽어주셔서 감사합니다! 오타 및 잘못된 내용은 언제든 댓글 달아주시면 최대한 빠르게 수정하겠습니다!