파이썬 알고리즘 173번 | [백준 11000번] -2 진수 - 최소힙

173. 강의실 배정

1) 어떤 전략(알고리즘)으로 해결?

• 강의실 배정은
  => 어떤 아이의 종료 시간이 내 시작 시간이랑 같거나 보다 클 때 그 방 이어서 쓸 수 있음,

2) 코딩 설명

<내 풀이>

import sys
import heapq

n = int(sys.stdin.readline().rstrip())
cnt = 0
heap=[]
for i in range(n) :
    #  N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능    
    s,e = (map(int, sys.stdin.readline().rstrip().split()))
    # 수업이 끝난 직후에 다음 수업을 시작
    heapq.heappush(heap, (s,e)) # 끝나는 시간을 기준으로 정렬 

room=[] #회의 종료 시간 담는 방 

# 회의가 끝나는 시간보다 다음 회의의 시작시간이 빠르면
# 회의실을 하나 추가로 개설
for j in range(n) :
    s,e = heapq.heappop(heap)
    # 1) 맨 처음(암 것도 없을 때)
    if not room : heapq.heappush(room, e)

    # 2) 맨 처음 방의 종료시간보다 같거나 크면 그 방에서 회의이어서 하기 오케이
    elif s >= room[0] : 
        # room[0] (맨 처음방의) 종료시간만 비교해도 되는 것은 ,
        # 맨 처음 방의 종료시간은 가장 작은 종료시간이기 때문,
        # 가장 작은 종료시간보다도 내 시작 시간이 작다? => 당연히 뒤에 종료시간들보다도 내가 작을테니 들어갈 방 없음
        # 이건 반드시 새 방 만들어야 하는 것이지
            heapq.heappop(room) #그방에서 이제 내가 회의 시작&종료, 이전 거 빼기
            heapq.heappush(room, e) #내 종료 시간 넣기 (힙 방식으로)

    # 3) 가장 작은 종료시간보다도 시작 시간이 작으면 (앞 방에서 다 빠꾸 먹은 것)  만들어야 하는 상태 
    else :
        heapq.heappush(room, e)
print(len(room))

<내 틀렸던 풀이, 문제점>

84%까지 갔는데 시간초과~

import sys
import heapq

n = int(sys.stdin.readline().rstrip())
cnt = 0
heap=[]

for i in range(n) :
    #  N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능    
    s,t = (map(int, sys.stdin.readline().rstrip().split()))
    # 수업이 끝난 직후에 다음 수업을 시작
    heapq.heappush(heap, (-t,-s)) #끝나는 시간을 기준으로 정렬 
    # print(heap)

room=[]

for j in range(n) :
    (s,e)= heapq.heappop(heap)
    s=-s
    e=-e
    #print(room)
    if not room :
        room.append(e)
    else :  
        for k in range(len(room)) :
            if room[k]>=s:
                room[k]=e
                break
        else : room.append(e)

print(len(room))

• 이중 for문 돌리는 부분 또한 (room 탐색 부분) 우선순위 큐로 바꿔야 할 듯

import sys
import heapq

n = int(sys.stdin.readline().rstrip())
cnt = 0
heap=[]

for i in range(n) :
    #  N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능    
    s,t = (map(int, sys.stdin.readline().rstrip().split()))
    # 수업이 끝난 직후에 다음 수업을 시작
    heapq.heappush(heap, (-t,-s)) # 끝나는 시간을 기준으로 정렬 

#[(-9, -6), (-8, -7), (-5, -2), (-3, -1), (-6, -4)]

room=[]

for j in range(n) :
    (e,s)= heapq.heappop(heap) # ROOT NODE 빼오기
    s=-s # 마이너스로 저장해서 다시 양수로 변경 
    e=-e 
    if not room : # room이 없다면 , 태초의 room을 더해
        heapq.heappush(room, -s) 
        #room 안에서도 정렬할거임, heap으로 처리, 시작 시간 넣어
    else :  
        for k in range(len(room)) :
            if -room[k]>=e:
                room[k]=-s
                break
        else : heapq.heappush(room, -s) 

print(len(room))

• 마찬가지 시간초과 ㅋ (바뀐게 없으니,, 당욘)

import sys
import heapq

n = int(sys.stdin.readline().rstrip())
cnt = 0
heap=[]

for i in range(n) :
    #  N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능    
    s,t = (map(int, sys.stdin.readline().rstrip().split()))
    # 수업이 끝난 직후에 다음 수업을 시작
    heapq.heappush(heap, (-t,-s)) # 끝나는 시간을 기준으로 정렬 

#[(-9, -6), (-8, -7), (-5, -2), (-3, -1), (-6, -4)]

room=[]

for j in range(n) :
    (e,s)= heapq.heappop(heap) # ROOT NODE 빼오기
    e=-e # 마이너스로 저장해서 다시 양수로 변경 
    if not room : # room이 없다면 , 태초의 room을 더해
        heapq.heappush(room, s) 
        #room 안에서도 정렬할거임, heap으로 처리, 시작 시간 넣어
    else :  
        for k in range(len(room)) :
            if -room[k]>=e: #이전 시작 시간이, 내 끝남 시간보다 크거나 같으면 이어지기 가능 
                room.pop(k) #k번째 원소빼기
                heapq.heappush(room, s) #내 걸 넣는데, 최대 힙으로 넣기 
                break
        else : heapq.heappush(room, s) #내 끝남시간보다 작으면 별도의 room 만들기 

print(len(room))

• room을 힙으로 바꾸어보았는데도, 여전히 시간초과!
• 당연히 이중 for문 문제

for j in range(n) :
    (e,s)= heapq.heappop(heap) # ROOT NODE 빼오기
    e=-e # 마이너스로 저장해서 다시 양수로 변경 
    if not room : # room이 없다면 , 태초의 room을 더해
        heapq.heappush(room, s) 
        #room 안에서도 정렬할거임, heap으로 처리, 시작 시간 넣어
    else :  
        for k in range(len(room)) :
            if -room[k]>=e: #이전 시작 시

• 이중 for 문을 없애도 되니 없애보자꾸나

<반성 점>

<배운 점>