➊ 서론
① 문제
컴퓨터가 있는 자리에는 1번부터 순서대로 번호가 매겨져 있다. 모든 사람은 싸지방에 들어왔을 때 비어있는 자리 중에서 번호가 가장 작은 자리에 앉는 것이 규칙이다.
준하가 발견한 사실과 이용 규칙을 가지고, 모든 사람이 기다리지 않고 싸지방을 이용할 수 있는 컴퓨터의 최소 개수와 자리별로 몇 명의 사람이 사용했는가를 구하시오.
첫째 줄에 사람의 수를 나타내는 N이 주어지고,
N개의 줄에 걸쳐서 각 사람의 컴퓨터 이용 시작 시각 P와 종료 시각 Q가 주어진다.
② 처음 풀이 (시간 초과)
컴퓨터 이용 시작 시각과 종료 시각을 튜플 형식으로 입력 받고 schedule 리스트에 저장하였다.
그리고 1순위 시작 시각, 2순위 종료 시각을 기준으로 리스트를 오름차순으로 정렬하였다.
먼저 싸지방에 도착한 사람의 순서대로 컴퓨터에 앉히고
이용 중인 각 컴퓨터의 종료 시간을 computer_end_time에 저장하였다.
이때 새로 싸지방에 도착한 사람은 이용이 끝난 컴퓨터가 있는지 확인하는 단계를 거쳐야 했는데 이중 for문을 사용하니 시간 초과가 발생하였다.
처음 풀이 ⬇️
import sys
input = sys.stdin.readline
N = int(input())
schedule = []
computer_end_time = [0] * N
computer_count = [0] * N # 자리 차있는지 여부
for _ in range(N):
start, end = map(int, input().split())
schedule.append((start, end))
schedule.sort(key=lambda x: x[1]) # 종료 시각을 기준으로 정렬
schedule.sort(key=lambda x: x[0]) # 시작 시각을 기준으로 정렬
for start, end in schedule:
for i in range(N):
# 이용이 끝난 컴퓨터가 있는지 확인
if computer_end_time[i] <= start:
computer_end_time[i] = end
computer_count[i] += 1
break
# 출력
result = []
for i in range(N):
if computer_count[i] == 0:
break
result.append(computer_count[i])
print(len(result))
print(*result)기존의 풀이는 O(n^2)의 시간복잡도를 갖고 있기 때문에
이용이 끝난 컴퓨터가 있는지 확인하는 작업의 시간을 줄일 필요가 있었다.
➋ 최소 힙을 이용한 풀이
그렇다면 현재 사용 중인 컴퓨터를 최소 힙에 넣고
종료 시간을 기준으로 자동 정렬되게 하면 어떨까?
기존에는 for문을 통해 종료된 컴퓨터가 있는지 하나씩 살펴봐야 했지만
최소 힙을 사용한다면 O(logN)의 시간복잡도로
종료 시간이 빠른 컴퓨터 순으로 접근할 수 있다!
따라서 가장 종료 시간이 빠른 heap[0]을 확인하여 컴퓨터에 앉을 수 있는지 확인한다.
만약 종료된 컴퓨터가 2대 이상 존재한다면 어디에 앉아야 할까?
최소 힙에 50분, 100분에 사용 종료되는 컴퓨터(총 2대)가 있고
100분부터 컴퓨터를 사용할 사람이 들어온다고 해보자.
heap[0]에 접근하여 2번 컴퓨터를 사용해야 할까?
🚨 아니다!
문제를 자세히 읽어보면 아래와 같은 문장이 있다.
"모든 사람은 싸지방에 들어왔을 때 비어있는 자리 중에서 번호가 가장 작은 자리에 앉는 것이 규칙이다."
따라서 사용 종료된 컴퓨터들을 다시 순회해서 번호가 가장 작은 컴퓨터에 앉아야 한다.
하지만 위와 같은 방법은 다시 순차적으로 탐색해야하므로 또 시간 초과가 발생한다.
그렇기 때문에 사용 종료된(사용 가능한) 컴퓨터들을 모아두는 최소 힙이 필요하다!
결국 이 문제에서 최소 힙을 2개 사용할 필요가 있다!
사용 종료된 컴퓨터들을 번호를 기준으로 오름차순 정렬되도록 최소 힙에 삽입한다.
즉, 전체 프로세스는 다음과 같다!
① 일찍 온 사람 순서대로 컴퓨터에 앉는다. (바깥 for문)
② use_computer에서 사용 종료된 컴퓨터가 존재하는지 확인하고
존재한다면 available_computer 최소 힙에 삽입한다.
③ available_computer에 컴퓨터가 있다면
available_computer[0] 컴퓨터에 사람을 앉힌다.
④ available_computer가 비어있다면 새로운 자리에 앉힌다.
⑤ 사람을 앉히고 use_computer 최소 힙에 삽입한다.
➌ 전체 코드
import sys
import heapq
input = sys.stdin.readline
N = int(input())
schedule = []
use_computer = []
available_computer = [] # 사용 가능한 컴퓨터
computer_count = [0] * N # 컴퓨터 이용한 사람 수
for _ in range(N):
start, end = map(int, input().split())
schedule.append((start, end))
schedule.sort(key=lambda x: x[0]) # 시작 시각을 기준으로 정렬
count = 0
for start, end in schedule:
# 사용 가능한 컴퓨터 갱신
while use_computer and use_computer[0][0] <= start:
temp = heapq.heappop(use_computer)
# 번호가 가장 작은 자리에 앉도록 최소 힙에 삽입
heapq.heappush(available_computer, temp[2])
# 사용 가능한 컴퓨터가 있다면
if available_computer:
index = heapq.heappop(available_computer)
computer_count[index] += 1
heapq.heappush(use_computer, (end, start, index))
# 사용 가능한 컴퓨터가 없다면
else:
computer_count[count] += 1
heapq.heappush(use_computer, (end, start, count))
count += 1
print(count)
print(*computer_count[:count])