[BJ]1655 가운데를 말해요

BJ G2 1655 가운데를 말해요

 

 

문제링크

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

1655번: 가운데를 말해요

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/BOnNK-NiPIs

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Collections;
import java.util.PriorityQueue;

/**
 * @author 은서파
 * @since 2022/05/30
 * @see
 * @git
 * @youtube
 * @performance 34916	404
 * @category #
 * @note
 */

public class BJ_G2_01655_가운데를말해요 {
    private static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder output = new StringBuilder();

    private static int N;
    private static PriorityQueue<Integer> maxPq, minPq;
    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
        N = Integer.parseInt(input.readLine());
        maxPq = new PriorityQueue<>(Collections.reverseOrder()); // 역순(큰 값 부터 나올 수 있게)
        minPq = new PriorityQueue<>();                           // 작은 값이 맨 앞에

        boolean isOdd = true;
        for(int n=0; n<N; n++){
            int num = Integer.parseInt(input.readLine());
            if(isOdd){
                maxPq.offer(num);
            }else{
                minPq.offer(num);
            }
            // 자리 교환 필요
            if(!minPq.isEmpty() && maxPq.peek() > minPq.peek()){
                minPq.offer(maxPq.poll());
                maxPq.offer(minPq.poll());
            }
            // 중간값은 왼쪽 maxPq에 존재
            output.append(maxPq.peek()).append("\n");
            isOdd = !isOdd;
        }
        System.out.println(output);
    }

    // REMOVE_START
    private static String src = "7\n"
                                + "1\n"
                                + "5\n"
                                + "2\n"
                                + "10\n"
                                + "-99\n"
                                + "7\n"
                                + "5";
    // REMOVE_END
}