[BOJ/백준] 12764 싸지방에 간 준하

 

import sys
import heapq
input = sys.stdin.readline

N = int(input())
heap = []
init_list = [list(map(int,input().split())) for _ in range(N)]

init_list.sort()
result = [0 for _ in range(100001)]
INF = float('inf')
for start_time,end_time in init_list:
    if heap:
        if heap[0] <= start_time:
            heapq.heappop(heap)
        heapq.heappush(heap,end_time)
    else:
        heapq.heappush(heap,end_time)
total_cnt = len(heap)
print(total_cnt)

check_number = []
min_chair_number = []
for start_time,end_time in init_list:
    if check_number:
        while check_number and check_number[0][0] <= start_time:
            _,pop_idx = heapq.heappop(check_number)
            heapq.heappush(min_chair_number,pop_idx)
        if not min_chair_number:
            idx = len(check_number)
            heapq.heappush(check_number,(end_time,idx))
            result[idx] += 1
        else:
            idx = heapq.heappop(min_chair_number)
            heapq.heappush(check_number,(end_time,idx))
            result[idx] += 1
    else:
        result[0] += 1
        heapq.heappush(check_number,(end_time,0))
print(*result[:total_cnt])

첫번째 풀이는 다음과 같다.

 

먼저 전체 컴퓨터의 개수를 구해준다.

 

check_number에는 끝시간과 사용하고 있는 사람이 있는 컴퓨터의 index를 넣어준다.

 

그리고 시작시간보다. 끝나는시간이 먼저 끝났을때에는 그걸 min_chair_number에 빈 컴퓨터의 index를 넣어준다.

 

 

만약 이미 들어차있는 check_number에 현재 시작시간보다 작은것이 하나도 없다하면,

 

먼저 min_chair_number가 있으면 min_chair_number에서 빈자리를 꺼내서 check_number에 넣어준다.

 

그리고 min_chair_number가 없으면 현재 주어진 컴퓨터에서 전부 자리가 꽉찬거이므로, 새 컴퓨터를 발급해주고,

 

그 값을 check_number에 넣어주면 된다.

 

 

 

import sys
import heapq
input = sys.stdin.readline
N = int(input())
time_list = []
for i in range(N):
    start_time,end_time = map(int,input().split())
    heapq.heappush(time_list,(start_time,i))
    heapq.heappush(time_list,(end_time,i))
isSeatperson = [-1]*N
seat_info = []
com_idx = 0
min_com_list = []

while time_list:
    _,person_number = heapq.heappop(time_list)

    if isSeatperson[person_number] == -1:
        if min_com_list:
            isSeatperson[person_number] = heapq.heappop(min_com_list)
        else:
            isSeatperson[person_number] = com_idx
            com_idx += 1
    else:
        heapq.heappush(min_com_list,isSeatperson[person_number])
        seat_info.append(isSeatperson[person_number])


max_com = max(seat_info)+1

result = [0]*max_com

for com_number in seat_info:
    result[com_number] += 1

print(max_com)
print(*result)

 

좀 더 깔끔한 풀이는 다음과 같다.

 

시작시간과 끝시간을 두개로 나눠서 time_list에 넣어준다.

 

그리고 난뒤에 하나씩 꺼내주면서, 만약에 이 사람이 앉을때 즉 start_time일때에는 min_com_list에 남은게 있으면,

 

하나를 출력해서 배정을 시켜준다.

 

그리고 그게 아니면 새로운 컴을 발급시켜주고, 그때의 idx를 증가시켜준다.

 

그리고 퇴실할때 나간 사람의 자리를 넣어준다.

 

그리고 마지막으로 그 사람이 앉았던 자리 정보를 seat_info에 저장시켜준다.

 

이렇게 전체 자리수를 구하고, seat_info를 통해 각 자리마다 앉았던 사람들의 정보를 저장시켜준다.