[백준 - Python] 12764 - 싸지방에 간 준하

0.  문제 링크

 

 

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

12764번: 싸지방에 간 준하

---

1.  풀이 방법

 

 

우선순위 큐를 3개나 사용해서 풀었음  
첫 번째는 시작 시간 순서대로 정렬한 리스트 - A  
두 번째는 끝나는 시간을 기준으로 정렬한 리스트 - B  
세 번째는 자리의 번호를 정렬한 리스트임 - C  

A에서 시간을 뽑음  
그리고 B에 넣고, C에서 가장 작은 자리의 번호를 추출함  
그 다음에 가장 작은 자리의 번호를 인덱스로 해서 p[index] += 1을 함

그 다음에 시간을 뽑을 때, 뽑은 애의 시작 시간이 B에 있는 가장 작은 값과 비교함  
그리고 시작 시간보다 작은 애들이 없을 때까지 모두 뽑아서 C에 넣음  

 

이를 계속해서 반복함

---

2.  코드

 

 

import sys
import heapq
input = sys.stdin.readline


if __name__ == "__main__":
    n = int(input())
    maps = []
    pc = [0] * (n + 1)
    for _ in range(n):
        heapq.heappush(maps, list(map(int, input().split())))

    end_time = []
    can_use = [*range(n)]       # 자리의 리스트

    while maps:
        s, e = heapq.heappop(maps)
        while end_time and s > end_time[0][0]:      # 현재 시작 시간보다 빨리 끝나는 자리가 있다면 모두 pop 함
            _, idx = heapq.heappop(end_time)
            heapq.heappush(can_use, idx)        # 앉을 수 있는 자리의 리스트에 넣음
        index = heapq.heappop(can_use)
        heapq.heappush(end_time, [e, index])        # 끝나는 시간 리스트에 넣음
        pc[index] += 1

    for i in range(n + 1):
        if pc[i] == 0:
            print(i)
            print(*pc[:i], sep=' ')
            break

---

3.  마무리