파이썬 알고리즘 176번 | [백준 19598번] 최소 회의실 개수 - HEAP

Yunny.Log ·2022년 6월 15일

Algorithm

목록 보기

179/318

176. 최소 회의실 개수

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

2) 코딩 설명

시간 담는 것은 시작 시간 기준으로 담고
방 만드는 것 비교는 최소 종료 시간 기준이 맞지

<내 풀이>


import heapq
import sys

n = int(sys.stdin.readline().rstrip())

times=[] #s,t 담아놓을 공간 (작은 시작시간부터)
room=[]

for i in range(n) :
    s,e = map(int, sys.stdin.readline().rstrip().split())
    times.append((s,e)) # 끝시간, 시작 시간으로 넣어둠

# times 에는 시작 시간이 작은 아이들부터 쭉 정렬 
times.sort()

# 시간 정렬은 시작 시간 기준으로 정렬 필요 ! (끝 시간 정렬하면 X)
# 방 정렬은 끝 시간 기준 정렬 (root 에 최소 종료 시간 오게)

for i in range(n) :
    s,e = times[i] 

    if not room : # 방에 암 것도 없으면 방하나 디폴트로 생성 
        room.append((e,s)) # 방에서는 root에 종료 시간 가장 빠른 것 와야 해
    else :
        # room은 힙이라 맨 앞에 있는 애가 최소 회의 end 시간
        smallestEnd, start = room[0] 

        # 최소 종료 시간의 회의실 끝나는 시간이 내 시작 시간보다 크면 
        # 기존 방들의 끝나는 시간은 내 시작 시간보다 모두 큰 상태
        # 따라서 new 방 필요
        if smallestEnd > times[i][0] : 
            # 새로 방 만들어주기
            heapq.heappush(room, (e,s) )

        else : # 아니라면 그 회의실은 내꼬
            # 회의시간은 내가 이어 넘겨받기
            heapq.heappop(room) #기존 회의실 시간 나로 대체할 거니깐 없애고
            heapq.heappush(room, (e,s)) # 대체재로 내 시간 넣기

print(len(room))

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

끝나는 시간을 기준으로 비교하면 틀린다


import heapq
import sys

n = int(sys.stdin.readline().rstrip())

times=[] #s,t 담아놓을 공간 (작은 시작시간부터)
room=[]

for i in range(n) :
    s,e = map(int, sys.stdin.readline().rstrip().split())
    times.append((e,s)) # 끝시간, 시작 시간으로 넣어둠

# times 에는 끝 시간이 작은 아이들부터 쭉 정렬 
times.sort() # times => [(10, 5), (30, 15), (40, 0)]

for i in range(n) :
    if not room : # 방에 암 것도 없으면 방하나 디폴트로 생성 
        room.append((times[i]))
    else :
        # room은 힙이라 맨 앞에 있는 애가 최소 회의 end 시간
        smallestEndTime, start = room[0] 

        # 회의실 끝나는 최소 시간이 내 시작 시간보다 크면 
        # 기존 방들의 끝나는 시간은 내 시작 시간보다 모두 큰 상태
        # 따라서 new 방 필요
        if smallestEndTime > times[i][1] : 
            # 새로 방 만들어주기
            heapq.heappush(room, times[i] )

        else : # 아니라면 그 회의실은 내꼬
            # 회의시간은 내가 이어 넘겨받기
            heapq.heappop(room) #기존 회의실 시간 나로 대체할 거니깐 없애고
            heapq.heappush(room, times[i]) # 대체재로 내 시간 넣기

print(len(room))

# [(10, 5)] 처음 디폴트
# [(30, 15)] 10 이라는 끝나는 시간이 내 시작 시간보다 작음
# [(30, 15), (40, 0)] 맨 앞에 있는 애가 최소 끝 시간인데, 내 시작시간보다 큼
#  => 그말이 즉슨 뒤 다른 방의 끝 시간들도 내 시작 시간보다 크다는 것 => 새 방 만들기