[BOJ] 12764번: 싸지방에 간 준하

copyrat90·2022년 4월 6일
0

PS

목록 보기
5/5

문제 설명

각 사람마다 PC 사용 시작시간 & 종료시간이 주어지고,
항상 빈 PC 중 idxidx가 가장 낮은 PC를 사용할 때,
1. 필요한 PC의 총 개수2. 각 PC별 사용 횟수를 구하시요.

접근 방법

1. Naive O(N2)O(N^2) 풀이

우선 시작하는 시간이 낮은 순으로 입력을 정렬한다.

idx01234
A[idx](10, 100)(20, 50)(30, 120)(60, 110)(80, 90)

이제 어떻게 해야 할 지 생각해보자.

일단 각 PC가 몇분까지 점유되는지 현황표pc_usage가 필요할 것이다.
그리고 각 PC별 사용 횟수pc_cnt도 따로 기록해야 한다.

우선, idx=0idx=0번째 사람을 보면, 처음이라 PC가 1대도 없으므로, PC 1대를 늘리고 100분까지 사용한다.

i0
pc_usage[i]100
pc_cnt[i]1

다음으로, idx=1idx=1번째 사람은, 20분부터 사용해야하는데,
i=0i=0번 PC는 그 시점에서 아직 사용중이므로, PC 1대를 늘리고 50분까지 사용한다.

i01
pc_usage[i]10050
pc_cnt[i]11

idx=2idx=2번째 사람, 30분부터 사용, 모든 PC 사용중, PC 1대 늘리고 120분까지 사용.

i012
pc_usage[i]10050120
pc_cnt[i]111

idx=3idx=3번째 사람의 경우, 60분부터 사용하는데, i=1i=1번 PC가 50분까지 사용되므로, 이제 그 자리가 비었다.
고로 i=1i=1번 자리를 110분까지 사용한다.

i012
pc_usage[i]100110120
pc_cnt[i]121

idx=4idx=4번째 사람, 80분부터 사용, 모든 PC 사용중, PC 1대 늘리고 90분까지 사용.

i0123
pc_usage[i]10011012090
pc_cnt[i]1211

이제 PC가 4대 필요하다는 것과, 각 pc_cnt[i]를 출력하면 된다.

그런데 이번 시작 시간에 빈 자리를 어떻게 찾아야 할까?

Naive 하게 i=0..len(pc_usage)i=0..len(pc\_usage)까지 순서대로 선형 탐색하며 종료됐는지 판단하면,
각자 개인 컴퓨터가 필요한 최악의 경우, O(N)O(N)개를 뒤져봐야 한다.
모든 사람을 이렇게 보면 O(N2)O(N^2) 으로 N100,000N\le100,000 에선 시간 초과이다.

2. O(NlogN)O(N \log N) 최적화

아이디어

pc_usage 표에서 이번 시작 시간보다 작은 종료 시간을 어떻게 O(N)O(N) 안에 찾을까?
선형 탐색으론 안되니, 표에서 종료 시간이 낮은 값부터 보는 게 좋겠다.

가만... 이거 다익스트라 알고리즘 에서의 상황과 비슷하다.
거기선, 표에서 낮은 값을 보려고 최소 힙으로 최솟값을 찾았다.
고로 pc_usage최소 힙으로 선언하면 되겠다.

그런데 이 문제에는 고려할 게 1가지 더 있다.
해당 시점에 사용 가능해진 PC는 여러 대가 있을 수 있는데, 그 중 PC 번호가 제일 작은 PC를 써야 한다.
pc_usage 최소 힙에서 최솟값을 찾았다고 쳐도, 그게 번호까지 가장 작은 PC는 아닐 수 있다.

해법

그래서 내가 해결한 방법은 이렇다.
일단 pc_usage 최소 힙에는 PC의 번호 ii를 포함해 (end_time,i)(end\_time, i) 튜플을 저장한다.

idxidx번째 사람을 시도할 때, 이제부터 사용 가능한 PC를 전부 pc_usage 최소 힙에서 뺀다. (반복문)
빼면서, 이번에 사용 가능해진 ii번을 available_pc 라는 또 다른 최소 힙에 넣는다.

available_pc.top() 을 꺼내면, 현재 사용 가능한 PC 중 번호가 가장 작은 놈이 나올 것이다.
만일 available_pc 가 비어있다면, 그건 PC를 추가 설치해야 하는 상황이니, PC 늘리는 처리를 하자.

시간 복잡도 분석

입력을 정렬하는 데 O(NlogN)O(N\log N) 걸린다.
그리고, 2개의 최소 힙 모두, 최대 O(N)O(N)개까지 원소가 들어갈 수 있다.

  1. pc_usage : NN명 각자 개인 PC가 필요한 최악의 상황이면, 힙에 NN개까지 동시에 존재.
  2. available_pc : N1N-1명까지 개인 PC가 필요하고, 남은 11명이 나머지 모든 사람보다 늦게 이용하는 경우,
    사용 가능한 PC N1N-1개 중 골라야 하므로 힙에 N1N-1개까지 동시에 존재.

힙에 NN개의 원소를 넣는데도 마찬가지로 O(NlogN)O(N\log N)의 시간이 걸리므로,
종합해서 최악 O(NlogN)O(N\log N)의 시간이 걸린다.

정답 코드: O(NlogN)O(N\log N)

profile
요새 알고리즘 문제 푸는 초보A

0개의 댓글