백준_가운데를 말해요_1655

// 알고리즘

 

1. 자료구조활용 문제

 

2. 우선순위큐 사용

 - 중간값을 구하기 위해 min우선순위큐와 max우선순위큐 2개 사용

 - 우선순위큐의 크기가 같으면 두개의 peek값을 비교하여 값 선정 

 - min의 peek 값과 max의 peek값을 비교하여 min 값이 더 작으면 자리교체

 

3. StringBuilder에 max.peek 값 저장 

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

public class 가운데를말해요_1655 {
	static int N;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> max = new PriorityQueue<>((o1, o2) -> o2 - o1);
		PriorityQueue<Integer> min = new PriorityQueue<>();
		StringBuilder sb = new StringBuilder();

		max.add(Integer.parseInt(br.readLine()));
		sb.append(max.peek() + "\n");

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

			if (min.size() == max.size()) max.add(num);
			else min.add(num);
			if (search(max.peek(), min.peek(), sb)) {
				int m = min.poll();
				int n = max.poll();
				max.add(m);
				min.add(n);
			}
			sb.append(max.peek() + "\n");
		}

		System.out.println(sb.substring(0, sb.length() - 1).toString());

	}

	private static boolean search(Integer maxNum, Integer minNum, StringBuilder sb) {
		if (maxNum > minNum) {
			return true;
		} else {
			return false;
		}
	}

}

 

※ 출력을 한 번에 하지 않고 매번 System.out.print를 했더니 계속 시간초과가 나는거였음... 출력도 신경써서 해야할거같음.