백준 12764. 싸지방에 간 준하

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

12764번: 싸지방에 간 준하

 

이 문제는 우선순위 큐를 사용해야하는데 두 개의 우선순위 큐를 이용하는 문제였다.

 

입력으로 사람들의 이용 시작시간과 종료시간이 주어진다.

우리는 모든 사람들이 기다리지 않고 싸지방을 이용할수 있도록 남는 자리가 없다면 컴퓨터의 갯수를 늘려나가고, 자리가 있다면 그 자리에 새로 온 사람을 앉혀야 한다. 

여기서 남는 자리가 있을때 주의할 점은, 남는 자리가 여러개 일때 번호가 가장 작은 자리에 새로온 사람을 앉혀야 한다는 것이다. 

 

따라서 두개의 우선순위 큐를 만들어야 하는데, 

첫 번째는 현재 싸지방 이용중인 인원이 끝나는 시간과, 컴퓨터 번호가 담긴 우선순위 큐 pq. (끝나는 시간 기준 min heap) 

두 번째는 현재 사용가능한 컴퓨터가 담긴 우선순위 큐 available 이다. (min heap) 

 

이제 모든 사람들을 하나씩 앉혀보면 되는데, 먼저온 사람부터 순서대로 앉혀야 하기 때문에 주어지는 입력을, 시작시간 기준으로 오름차순 정렬해야 한다.

 

 

첫 번째 사람은 우선 컴퓨터 한대를 만들어서 자리를 주고, 우선순위 큐에 넣어주면 된다.

 

두 번째 사람부터는 계산을 해봐야 한다.

우선 우선순위 큐에는 현재 싸지방을 이용중인 사람들의 끝나는 시간이 담겨있는데, 현재 이용하려는 사람의 시작시간 보다 작은 경우, 이미 이용이 끝난 인원들이므로 우선순위 큐에서 모두 빼준다. 

또한 이용시간이 끝난 사람들을 우선순위 큐에서 빼줄때 그 사람들의 자리는 반납되는데, 이 자리들의 번호도 또 다른 우선순위 큐 available에 푸쉬한다.

이렇게 되면 우선순위 큐  pq 에는 아직까지도 싸지방을 이용중인 사람들만 남게되고, available에는 반납되어 앉을수 있는 자리들이 남게된다.

 

이제 새로 온 사람을 앉히면 되는데, available이 비어있다면 비어있는 자리가 없기 때문에 새로운 자리를 늘리면 되고, 

available에 요소가 있다면 그 자리에 앉히면 된다. 

available도 min heap이기 때문에 비어 있는 자리들중 번호가 가장 작은 자리에 앉게 된다.

 

 

 

주의할점:

- 모든 사람은 싸지방에 들어왔을 때 비어있는 자리 중에서 번호가 가장 작은 자리에 앉는 것이 규칙이다.