백준 가운데를 말해요(1655)

 

자료구조 문제 풀어보기~

 

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

1655번: 가운데를 말해요

 

문제의 포인트는 중간값을 계속 유지해야한다.

 

무식하게 다 넣어놓고 정렬하면 시간초과의 길....

 

중간값을 유지하는 방법은 우선순위 큐를 두개를 이용하면 된다.

 

양쪽에 번걸아가며 넣으며 중간값을 계속 유지해두면 된다.

 

 

package struct;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * https://www.acmicpc.net/problem/1655
 */
public class Q1655 {

    public static void main(String[] args) throws IOException {
        struct();
    }

    public static void struct() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        PriorityQueue<Integer> min = new PriorityQueue<>();
        PriorityQueue<Integer> max = new PriorityQueue<>((o1, o2) -> o2 - o1);
        int n = Integer.parseInt(br.readLine());
        for (int i=0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());

            if (i % 2 == 0) {
                max.add(num);
            } else {
                min.add(num);
            }

            if (!max.isEmpty() && ! min.isEmpty()) {
                if (max.peek() > min.peek()) {
                    int temp = max.poll();
                    max.add(min.poll());
                    min.add(temp);
                }
            }

            bw.write(max.peek() + "\n");
        }

        bw.flush();
        bw.close();
    }
}

 

결과