[백준] No.1655 - 가운데를 말해요 (C++, 우선순위 큐)

문제

 

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

1655번: 가운데를 말해요

 

풀이

 

solved.ac 난이도: Gold 3

 

종만북에 등장하는 변화하는 중간 값 문제와 동일한 문제.

해당 책에서의 트립 알고리즘을 사용하여 트리 내의 몇 번째 원소를 반환하는 코드를 짤 수도 있지만 우선순위 큐만으로 해결가능하다.

 

우선순위 큐는 부모 노드가 자식 노드보다 큰 값만 가지게 정렬(최대 힙의 경우)되어 있다.

반대로 최소 힙으로 구현된 우선순위 큐는 부모 노드가 자식 노드보다 작은 값을 갖는다.

이를 이용하여 오름차순으로 정렬했을 때 처음부터  중간값 까지를 최대 힙에 저장하자.

이럴 경우 최대 힙의 top이 말해야 하는 중간 값이 된다.

 

중간값 이후부터 끝 값까지는 최소 힙에 저장하자.

만약 새로운 수가 최소 힙의 top보다 크다면 최소 힙 쪽에 포함되어야 한다.

하지만 이런 경우 최소 힙 쪽이 중간값부터 끝 값까지의 범위를 저장하게 된다.

따라서 최소 힙의 top을  최대 힙으로 넘겨주어야 서로의 포함 범위의 크기가 같아진다.

 

이를 정리해보자.

새로운 값을 n, 최소 힙으로 구현한 우선순위 큐를 min_pq, 최대 힙으로 구현한 우선순위 큐를 max_pq라고 하자.

max_pq는 항상 가장 작은 값부터 중간 값까지를 포함하기 때문에 새로운 수가 홀수 번째 수라면 이 수가 포함된 후 max_pq이 min_pq보다 크기가 1 더 커야 한다.

새로운 수가 짝수 번째 수라면 이 수가 포함된 후 min_pq와 max_pq의 크기는 같다.

 

1. 새로운 수가 홀수 번째 수

아직 n이 추가되기 전이므로 min_pq와 max_pq의 크기는 같은 상태이다.

따라서 n이 추가된 후라면 min_pq가 max_pq보다 1 더 커져야 된다.

 

1-1) n>min_pq.top() 

  n을 max_pq에 바로 넣으려 했지만 큰 수들의 힙인 min_pq의 top보다 n이 더 크다.

n을 max_pq에 넣게 되면 오히려 min_pq의  top이 중간 값이 된다.

따라서 두 수를 바꾸어 서로의 큐에 push 해주자.

 

1-2) 이외의 경우

n을 그대로 max_pq에 넣어주고 max_pq의 top이 중간 값이 된다.

만약 n이 max_pq 중에서 가장 크다면 중간 값이 될 것이고 아니라면 다른 가장 큰 값이 중간 값(top)이 된다.

 

2. 새로운 수가 짝수 번째

아직 n이 추가되기 전이므로 min_pq의 크기가 max_pq보다 1 더 큰 상태이다.

따라서 n이 추가된 후라면 min_pq와 max_pq의 크기가 같아져야 한다.

 

2-1) n<max_pq.top()

 n을 바로 min_pq에 넣으려 했지만 작은 수들의 힙인 max_pq의 top보다 n이 더 작다.

따라서 n은 max_pq에 삽입되어야 한다.

서로의 크기를 맞춰주기 위해 max_pq.top은 min_pq에, n은 max_pq에 push 해주자.

 

2-2) 이외의 경우

 n은 바로 mim_pq에 넣어주고 max_pq의 top이 여전히 중간 값이 된다.

 

 

시간제한이 굉장히 타이트하므로 입출력 연산자는 c타입으로 해주어야 시간 초과가 발생하지 않는다.

 

 

코드