[백준/자바] 1655 : 가운데를 말해요

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

1655번: 가운데를 말해요

---

문제를 보고 바로 우선순위 큐를 사용하면 되겠구나! 하고 생각했다.

하지만 우선순위 큐는 인덱싱 기능이 없어서 가운데 값을 어떻게 구해야 되나 헤매다

우선순위 큐를 빌 때까지 poll 해 temp 우선순위 큐에 넣고, 이를 List로 변환 후 인덱스를 통해 가운데 값을 구했다.

 

답은 제대로 출력됐지만 메모리 초과 때문에 실패했다😢

풀면서도 더 나은 방식이 있을 것 같아서 검색해 본 결과, 우선순위 큐를 2개 사용하면 된다는 것을 알았다.

 

중간값을 기준으로 최대힙, 최소힙으로 나누면 최대힙의 루트값이 중간값이 된다!

예를 들어 숫자가 1부터 5까지 있을 경우,

 

• 최대힙 : 3 2 1
• 최소힙 : 4 5

위처럼 나뉘므로, 최대힙의 루트값인 3이 중간값임을 알 수 있다.

 

풀이 과정은 다음과 같다.

 

• 최소힙과 최대힙의 크기가 같으면 최대힙, 다르면 최소힙에 원소를 넣는다.
  • 숫자가 홀수개일 경우, 중간값을 최대힙에 넣기 위해
• 최대힙의 루트값이 최소힙의 루트값보다 작으면 두 값을 바꾼다.
• 최대힙의 루트값을 출력한다.

최대힙은 PriorityQueue 생성자에 Comparater.reverseOrder()를 인수로 넣어주면 된다.

 

전체 코드

import java.io.*;
import java.util.*;

public class Boj_1655 {

   public static void main(String[] args) throws NumberFormatException, IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringBuilder sb = new StringBuilder();
   
       int N = Integer.parseInt(br.readLine());
   
       PriorityQueue<Integer> min = new PriorityQueue<Integer>();
       PriorityQueue<Integer> max = new PriorityQueue<Integer>(Comparator.reverseOrder());

       for (int i = 0; i < N; i++) {
           int n = Integer.parseInt(br.readLine());

           if (min.size() == max.size())
               max.add(n);
           else
               min.add(n);

           if (!min.isEmpty() && !max.isEmpty()) {
               if (min.peek() < max.peek()) {
                   int temp = min.poll();
                   min.add(max.poll());
                   max.add(temp);
               }
           }
           sb.append(max.peek() + "\n");
       }

       System.out.println(sb);
   }
}

---

우선순위 큐를 이용한 문제에서 중간값을 구해야 할 경우

여러 개의 우선순위 큐를 사용하는 방식 고려해 보기!