[백준] 11000번: 강의실 배정 - python

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

11000번: 강의실 배정

 

처음보고 회의실 문제랑 비슷하다고 생각해서 그 메커니즘으로 정렬 후 arr에 배열이 없을때까지 제거하면서 cnt를 증가시켜주는 방식으로 코드를 구현했다. 그러나 시간초과가 발생하면서 뇌정지가 왔다.

 

처음 짠 코드

n = int(input())

arr = []
for i in range(n):
    start, end = map(int, input().split())
    arr.append((start, end))

arr.sort(key=lambda x: (x[1], x[0]))

cnt = 0
while arr:
    max = 0
    for start, end in arr:
        if max <= start:
            max = end
            arr.remove((start, end))
    cnt+=1

print(cnt)

 

뭔가 remove 함수가 오래걸려서 에러가 발생하는거같은데..

 

import sys
input = sys.stdin.readline
n = int(input())

arr = []
ch = [0] * (n+1)
for i in range(n):
    start, end = map(int, input().split())
    arr.append((start, end))

arr.sort(key=lambda x: (x[1], x[0]))

cnt = 1
while max(ch) != 1:
    start = 0
    i=0
    for start, end in arr:
        i +=1
        if start <= start and ch[i] == 0:
            start = end
            ch[i] = 1
    cnt+=1

print(cnt)

 

혹시몰라서 check리스트를 생성하고 비교하는 방식으로 코드를 재구성하였으나 실패..

 

다시 생각하였는데 우선순위 큐에서 큰걸로 정렬한 뒤 작은거부터 삭제시키면서 큐를 구성하면 어떨까라는 생각을 하고있다.

생각은 했는데 구현하기가 너무 힘들었다. 그리고 우선순위를 빈 통으로 생각했어야되었는데 그렇게 하지 못했다.

그래서 우선순위를 쓰는 법을 공부하고 문제 풀이를 시작했다.

 

https://seongonion.tistory.com/91

[Python] heapq(우선순위 큐) 사용법

 

그럼에도 접근법이 쉽지 않았는다.

순서가 정해져있는 삭제를 할때 사용하면 좋을 것 같았다.

삭제와 삽입을 진행할때 트리의 높이까지 진행되므로 O(logN)으로 시간초과를 해결할 수 있다.

 

최소힙을 사용하였기 때문에 정렬은 x[0]으로 기준으로 설정해준뒤 코드를 작성했다.

 

아래는 최종 코드이다.

import heapq

n = int(input())
arr = []

for i in range(n):
    start, end = map(int, input().split())
    arr.append([start, end])

arr.sort()#시직하는 시간으로 정렬.

hq = []

heapq.heappush(hq, arr[0][1]) #가장 일찍 시작해서 끝나는시간 추가

for i in range(1, n):
    if arr[i][0] < hq[0]: #끝나는 시간이 시작하는 시간보다 크면
        heapq.heappush(hq, arr[i][1]) #끝나는 시간 추가
    else: #순서가 맞으면
        heapq.heappop(hq) #빼내고
        heapq.heappush(hq, arr[i][1]) #끝나는 시간 추가해준다. 

print(len(hq)) #이렇게 되면 마지막엔 회의실의 개수가 남는다.

 

완성..