[코테] 강의실 배정

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

문제요약:

n개의 줄에서 강의시간의 시작시간 s와 끝나는시간 e 가 주어진다. 모든 강의를 수강하기 위한 최소한의 강의실 개수를 구하시오.

 

난이도:

골드5

 

소요시간:

10분

 

제출횟수:

1회

 

코드:

import sys
input = sys.stdin.readline
from collections import defaultdict

n = int(input())
arr = defaultdict(int)
for _ in range(n):
    s,e = map(int,input().split())
    arr[s] +=1
    arr[e] -=1
    
M = 0
now = 0
for i in sorted(list(arr)):
    now += arr[i]
    M = max(now,M)

print(M)

맨 처음 이문제를 보았을 때 만약 숫자의 크기가 크지않다면 강의시간(s,e)의 최대  크기만큼 배열을 할당하고

arr[s] +=1 , arr[e] -=1 을 한뒤 (누적합) 앞에서 부터 쭉더하면서 최대값을 기억한뒤 답으로 출력했을 것입니다.

하지만 이문제는 강의시간(s,e) 의 범위가 10^9였기 때문에 그렇게 하면 시간 초과가 날것이라고 판단했고, 

강의 개수 n의 범위가 200,000 이었기 때문에 이를 활용 해야겠다고 생각했습니다.

defaultdict을 활용해서 중간에 비는것 없이 s와e로만 이루어진 list를 만들었고, 거기에 +1,-1을 해주었습니다. 이렇게 하면 그 defaultdict은 최대 길이가 400,000이기 때문에 (하나도 안겹쳤을 경우) 시간복잡도가 충분할 것이라고 판단했고, 

sorted(list(arr))을 이용해서 defaultdict의 key 값만 뽑아내서 now(현재값의합)을 만들었고, 그때끄때 이 현재값들중 최고값만 필요함으로 M을 갱신시켜 주었습니다. 그 후 M을 출력해주었습니다.

 

다른사람 코드:

import sys
import heapq
input = sys.stdin.readline

N = int(input())
time = []

for _ in range(N):
    time.append(list(map(int,input().split(' '))))
time.sort(key=lambda x : (x[0],x[1]))

heap = [time[0][1]]
for i in range(1,N):
    if heap[0] <= time[i][0]:
        heapq.heappop(heap)
    heapq.heappush(heap,time[i][1])

print(len(heap))

저는 그리디로 풀었으나 보통 위와 같은 방법으로 많이 푸신 듯 합니다. 먼저 전부 입력 받은뒤 오름차순으로 정렬해줍니다. 그 후 앞에서부터 끝나는 시간을 비교하면서 heapq에 넣는데, 만약 이미 들어가있는 것의 최소값(가장 먼저 끝나는강의) 보다 지금 시작하려는 강의가 더 늦게 시작한다면 그 앞의 강의가 끝난다음에 새로운 강의를 넣어주면 되기때문에 첫번째 강의를 빼주고, 그이후에 새로운 강의의 끝나는 시간을 넣어줍니다. 이렇게 하면 겹치지 않을때는 강의실을 비우고 새강의실을 들어가게되고 겹칠때는 heap의 크기가 늘어나기 때문에 다음과 같이 계산될 수 있습니다.