[BOJ 1655] 가운데를 말해요

문제

• BOJ 1655
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

이 문제는 풀기 전에 최소힙, 최대힙에 대한 개념 이해를 해야 풀 수 있는 문제이다.
첫 접근은 리스트에 값을 넣어줄때마다 정렬해서 가운데값을 구해주는 것으로 생각했는데, 입력값이 10만개이므로 매번 정렬해주면 시간초과가 나게 된다.
따라서 두개의 우선순위큐를 사용해 문제를 풀어주었다.

1. 최대힙(max)과 최소힙(min) 구조의 우선순위큐 2개를 생성한다.
2. 값을 입력받을 때 max와 min에 있는 사이즈를 비교해서 번갈아가며 넣어준다.
   • 처음 입력할 때는 max부터 넣어주어야 가운데값을 기준으로 max와 min이 내림차순된 구조를 가질 수 있음
3. max와 min에서 값을 꺼내서 max값 > min값이면 두 값을 서로 바꿔준다.
4. 가운데 값은 항상 max값이 되므로 StringBuilder에 누적 저장해준다.

그림으로 그려보면 쉽게 이해할 수 있는데..
지금 펜슬이 없어서 나중에 추가하겟듬.

import java.io.*;
import java.util.Collections;
import java.util.PriorityQueue;

//최소힙, 최대힙 개념 이해가 필요한 문제
public class Main {

    static int N;
    static int x;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        //가운데를 기준으로 내림차순(최대힙), 오름차순(최소힙)으로 나눠주기
        PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> min = new PriorityQueue<>();

        StringBuilder sb = new StringBuilder();

        for(int i=0; i<N; i++){
            x = Integer.parseInt(br.readLine());
            //max에 먼저 넣어주고, 번걸아가면서 넣어주기
            if(max.size() == min.size()) max.add(x);
            else min.add(x);

            //가운데값 구하기
            if(!max.isEmpty() && !min.isEmpty()){
                if(max.peek() > min.peek()){ //max값이 min값보다 크다면 바꿔줘야함
                    int tmp = min.poll();
                    min.add(max.poll());
                    max.add(tmp);
                }
            }
            sb.append(max.peek()+"\n");
        }

        System.out.println(sb+"");
    }
}