99클럽 코테 스터디 4기 19일차 TIL - 백준: 강의실(1374) Swift & Python

레일리·2024년 11월 16일

99클럽 코테 스터디 4기

목록 보기

19/35

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
백준	1374	강의실	그리디, 우선순위큐	골드5	Swift, Python

🚀 나의 접근 방법

첫 번째(Python) - 우선순위큐(힙)

먼저 입력받은 시간들을 시작 시간 기준으로 오름차순 정렬한다.

그리고 rooms라는 배열에 가장 첫 번째(시작 시간이 빠른) 시간의 끝나는 시간을 넣는다.

이후 정렬된 시간에 순서대로 접근하면서, 현재 접근 한 시간의 시작 시간(time[0])이 rooms에 있는 시간 중 가장 작은 시간(rooms[0])과 비교하여 크거나 같으면 rooms 배열(힙)에서 제일 작은 것을 제거하고 현재 시간의 종료 시간(time[1])을 넣는다.

즉, rooms라는 배열에 있는 강의 중 이미 끝난 강의가 있으면 그 강의를 제거하고 새로운 강의를 넣는 것이다. 이미 끝난 강의가 없다면 그냥 rooms에 강의를 추가한다.(새로운 방을 추가하는 것)

그러면 결국 마지막에 rooms 배열 요소의 개수가 필요한 최소 강의실 개수가 될 것이다.

이때 주의해야 할 점은 rooms 배열에서 제일 작은 값을 찾고 제거하는 방법이다.

처음에는 for문 돌 때마다 rooms를 내림차순 정렬(O(N))되게 했지만 이는 시간초과를 냈다. 즉, 정렬과 삽입 삭제에서 더 빨라져야 했다.

그래서 이때 필요한 것이 힙(우선순위 큐, 최소 힙) 자료구조이다. 힙을 사용하면 O(logN)의 시간에 삽입, 삭제가 가능하고 (최소 힙이라면) 저절로 오름차순으로 접근할 수 있다.

두 번째(Swift) - 정렬 및 구현

Swift에서는 힙 자료구조가 지원되지 않는다. 그래서 필요하다면 직접 구현해야 하지만 시간도 코드도 너무 많이 걸린다.

그래서 힙을 사용하지 않는 풀이를 찾았다. 원리의 핵심은 동시에 필요한 최대 강의실의 개수를 찾는 것이다.

먼저 입력받은 시간들을(시작, 끝나는 시간 상관없이) 오름차순 정렬해 줘야 한다. 하지만 만약 시간이 같다면 끝나는 시간이 먼저 앞에 오도록 정렬해야 한다. (이유는 간단하다 한 번 생각해 보자)

이후 정렬된 시간을 차례로 방문하면서 시작 시간이면 count를 +1 증가시키고 아니라면 -1 감소시킨다. 그리고 매번 maxCount에 count의 최댓값을 저장해 주면 답을 구할 수 있다.

✍️ 나의 코드

Swift

let N = Int(readLine()!)!

var times: [(Int, Bool)] = []
for _ in 0..<N {
    let input = readLine()!.split(separator: " ").map{ Int($0)! }
    times.append((input[1], true))
    times.append((input[2], false))
}

times.sort(by: { $0.0 == $1.0 ? !$0.1 && $1.1 : $0.0 < $1.0 })

var count = 0
var maxCount = 1
for (_, isStart) in times {
    if isStart {
        count += 1
    } else {
        count -= 1
    }
    maxCount = max(count, maxCount)
}

print(maxCount)

Python

import heapq

N = int(input())

times = []
for _ in range(N):
    num, start, end = map(int, input().split(" "))
    times.append([start, end])

times.sort()
rooms = [times[0][1]]
for time in times[1:]:
    if time[0] >= rooms[0]:
        heapq.heappop(rooms)
    heapq.heappush(rooms, time[1])

print(len(rooms))