[백준] 1655번 가운데를 말해요 [ 반드시 다시 풀어볼 것 ]

1655번: 가운데를 말해요

지금까지 값중 “중간값”

• 짝수개 → 더 작은 값 .

“지금까지” 라는게 문제임

1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야

• 하나를 외칠 때 마다, 동생도, 지금까지 값 중, 중간 값을 말해 줘야 함.

N의 개수는 10만개 이하.

풀이

일단 브루트 포스로 생각해보면

백준이가 수를 부를 때 마다(n번= 10만번 ), 정렬하고(nlogn), ⇒n^2logn , 중앙값찾기( size상 중간 값 or 를 한다면? → O(n^2logN) → 안됨

제한시간이 0.1 초 → 무조건.. 기존의 데이터를 사용해야하는 문제인듯하다.

규칙 을 찾고자 하였으나, 어차피 정렬을 해야만 했다.

풀지 못했음

감이 오지 않았다.

다른 사람들의 풀이를 봤는데 , 어떻게 저걸 생각한걸까

---

두 개의 우선순위 큐를 사용한다. 이 때 아래의 조건을 만족시켜준다.

• 두 개의 heap(우선순위 큐 ) 을 사용한다→ 하나는 min heap, 다른 하나는 max heap 을 사용한다.

  • 최소heap의 모든 값들 > max heap

    • 이를 만족하기 위해서는 min heap의 top > max heap 의 top 이어야 한다.

  • max heap의 사이즈 = min heap의 사이즈 or min heap의 사이즈 +1

    (중앙값을 구하기 위함. 전체 개수가 홀수인 경우, 중앙값은 항상 max heap에 있게 되고, 짝수인 경우에도 더 작은 값을 중앙값으로 한다하였으니 max heap에 있게된다 )

  • 값을 넣어줄 때 마다, min heap, max heap의 top 값을 비교 → min heap의 top < max heap의 top ⇒ 값을 교환.

    • 항상, min heap의 값들이 max heap의 값보다 크도록 유지해준다.

  • 이렇게 하면, max heap의 top값이 중간값이 된다.

위 조건을 만족시키기 위해서는 아래와같이 해야함

1. min크기 = max 의 크기→ max에 숫자를 추가한다.
2. min크기 < max의 크기 → min에 숫자를 추가한다.
3. 숫자를 추가 할 때 마다, min의 root 와 max의 root를 비교 → min 의 root가 max의 root보다 작은 경우 → 둘을 swap한다.
   • 여기서 while을 통해 여러번 swap 할 일이 생길까??? → Nope . 두 힙 중 하나에라도 수를 하나씩 추가할 때 마다, 비교를 하고 있기 때문에, max힙의 root가 min힙의 root보다 커지는 순간 마다, 둘 사이의 교환을 한다는 것은, 하나 이상의 차이가 생길 수 없어짐.

자바의 Priority Queue의 시간 복잡도

Java PriorityQueue (Java Doc)

O(log n) time for the enqueing and dequeing methods (offer, poll, remove() and add) ⇒ 따라서 n 개 넣는데에 O(nlogn)

O(n) for the remove(Object) and contains(Object) methods

O(1) for the retrieval methods (peek, element, and size)

시간초과

출력 문제로 인한 것이었다.

• 수를 추가할 때마다 System.out.println(maxHeap.poll()) 호출의 문제
  • 이거는 매번, String을 생성하는 것도 있음.
• StringBuilder 를 사용하는게 이 문제에서는 더 적절했던 듯 하다.
• BufferedWriter도 괜찮나? →노노..heap에서 꺼낸 Integer를 그냥 넘기면 안된다;; 숫자를 넘기면, character의 ascii code 값으로 여기게 된다. 따라서 잘못된 출력을 하게 되었던 것

  public void write(int c) throws IOException {
          synchronized(this.lock) {
              this.ensureOpen();
              if (this.nextChar >= this.nChars) {
                  this.flushBuffer();
              }
  
              this.cb[this.nextChar++] = (char)c;
          }
      }

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

public class Main {

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void solve() throws IOException{
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        int temp = 0;
        int min = 0 , max = 0;
        StringBuilder sb = new StringBuilder();
        for(int i =0;i<n;i++){
            temp = Integer.parseInt(br.readLine());
            // 1. 사이즈 비교
            if(minHeap.size() == maxHeap.size()) {
                maxHeap.add(temp);
            }
            else{
                minHeap.add(temp);
            }
            if(!minHeap.isEmpty() && !maxHeap.isEmpty()&&minHeap.peek() < maxHeap.peek()){
                min = minHeap.poll();
                max = maxHeap.poll();
                minHeap.add(max);
                maxHeap.add(min);
            }
            sb.append(maxHeap.peek()).append("\n");

        }
        System.out.println(sb);
    }
    public static void main(String[] args)throws IOException {
        solve();
    }
}