우선순위 큐1

• 

  [c++] 백준 - 1655 가운데를 말해요(우선순위 큐) 1. 문제 2. 입력 및 출력 3. 문제 해설 priority_queue를 적절히 사용하여 중간값을 찾아내면 되는 문제였다. 우선 중간값을 찾아야한다는 점에서 pq가 두 가지가 필요하다는 것을 알 수 있었다. 우리는 최대힙과 최소힙을 각각 하나씩 선언하여 중간을 찾아내면 된다. 그런데 문제에서 만약 짝수개가 들어갔을 경우에는 더 작은 값을 찾아내라 했으니 정답은 최대 힙에 들어있을 수 있을 것이다. 왜냐하면 pq에서 접근할 수 있고 의미가 있는 값은 pq.top()에 해당하는 부분이다. top()이 항상 답이 되게 하려면 우리는 다음과 같이 pq를 구성해야한다. 만약 1 5 2 10 이라는 수열을 기준으로 봤을 때 정렬을 하면 1 2 5 10이 되고 이 기준에서 중간값은 2에 해당한다. pq.top()이.. c++/알고리즘 2023. 2. 16.