문제 링크
https://www.acmicpc.net/problem/12764
🕒 Python 풀이시간: 20분
import heapq
n=int(input())
q=[]
for _ in range(n):
s,e=map(int,input().split())
heapq.heappush(q,(s,e))
seatNum=0
cnt=dict()
endQ=[]
empty=[]
while q:
s,e=heapq.heappop(q)
while endQ and endQ[0][0]<=s:
heapq.heappush(empty,heapq.heappop(endQ)[1])
if not empty:
seatNum+=1
if seatNum not in cnt:
cnt[seatNum]=1
else:
cnt[seatNum]+=1
heapq.heappush(endQ,(e,seatNum))
else:
k=heapq.heappop(empty)
if k not in cnt:
cnt[k]=1
else:
cnt[k]+=1
heapq.heappush(endQ,(e,k))
print(len(cnt))
for key in cnt.keys():
print(cnt[key],end=' ')싸지방 자리 배치: 최소 자리 수와 인원 계산하기! 🪑💻
싸지방에 갔을 때 준하가 아는 규칙에 따라 사람들이 앉을 때 필요한 최소 자리의 수와 그 자리에 앉은 사람의 수를 구하는 문제이다. 우선순위 큐를 이용하여 필요한 순으로 가져오는 문제이면서도 그리디(냅색문제)라고 할 수 있을 거 같다. 비슷한 유형을 보석 도둑에서 크게 데여봤다...
여담으로 친구들끼리 시간재고 누가먼저 풀기 해서 20분만에 급하게 풀어버렸다.
처음에 우리는 모든 사람들에 대해서 시작시간과 종료시간을 알고 있다. 이 때, 우리는 시작 시간 순으로 먼저 필요하므로 이를 우선순위 큐에 튜플로 묶어서 넣는다. 그리고 이 사람들이 전부 소진될 때까지 즉, 큐가 빌때까지 큐를 꺼내면 된다.
처음의 while문을 봐보자 빈 자리를 전부 구해내고 그 자리 중에서 가장 작은 자리를 가져와야 하므로 일단 끝난 사람들이 들어간 endQ에서 현재 사람이 시작하는 시간보다 일찍 끝난 사람들을 가져온다. 이 때 우리는 자리 번호만 이제 필요하므로 자리 번호만 우선순위 큐에 넣어준다.
그러면 이제 다 끝났다. 만약 빈자리가 있다면 즉, 빈자리 번호가 들어간 배열에 빈자리가 들어가 있다면 다른 사람이 쓰고 난 자리이기 때문에 해당 자리의 사용횟수를 늘려주고 현재의 사람의 끝나는 시간을 endQ에 넣는다. 만약 새로 빈 자리가 없다면 우리는 자리의 수를 최소화 시켜야 하므로 자리의 갯수를 늘려주면서 똑같이 처리해주면 된다.
이렇게 Python으로 백준의 "싸지방에 간 준하" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
