백준 1655. 가운데를 말해요

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

문제제목 : 가운데를 말해요

문제난이도 : 골드2

문제유형 : 우선순위큐

 

문제

수빈이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 수빈이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 수빈이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

출력

한 줄에 하나씩 N줄에 걸쳐 수빈이의 동생이 말해야하는 수를 순서대로 출력한다.

 

코드

(1) 노가다로 조건문을 찾아 쓴 코드

package week2;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.PriorityQueue;

public class BOJ1655 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); //최소힙 (1,2,3)
		PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder()); //최대힙 (30, 20, 10)
		
		int n = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < n; i++) {
			int num = Integer.parseInt(br.readLine());
			if (minHeap.size() == maxHeap.size()) {
				if (minHeap.size() == 0) {
					maxHeap.add(num);
				} else {
					if (num < minHeap.peek()) {
						maxHeap.add(num);
					} else if (num > minHeap.peek()) {
						minHeap.add(num);
						maxHeap.add(minHeap.poll());
					} else {
						maxHeap.add(num);
					}
				}
			} else {
				if (num < maxHeap.peek()) {
					maxHeap.add(num);
					minHeap.add(maxHeap.poll());
				} else  {
					minHeap.add(num);
				} 
			}
			bw.write(String.valueOf(maxHeap.peek()) + "\n");
		}
		bw.flush();
		bw.close();
	}
}
//bw.write("전체 " + maxHeap.toString() + " | " + minHeap.toString() + "중앙 " + String.valueOf(maxHeap.peek()));

(2) 블로그 참고 코드

package week2;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.PriorityQueue;
//블로그 코드 참고
public class BOJ1655_2 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); //최소힙 (1,2,3)
		PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder()); //최대힙 (30, 20, 10)
		
		int n = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < n; i++) {
			int num = Integer.parseInt(br.readLine());
			
			if (minHeap.size() == maxHeap.size()) {
				maxHeap.add(num);
			} else {
				minHeap.add(num);
			}
			
			if (!maxHeap.isEmpty() && !minHeap.isEmpty()) {
				if (maxHeap.peek() > minHeap.peek()) {
					int temp = maxHeap.poll();
					maxHeap.add(minHeap.poll());
					minHeap.add(temp);
				}	
			}
			bw.write(String.valueOf(maxHeap.peek()) + "\n");
		}
		bw.flush();
		bw.close();
	}
}
//bw.write("전체 " + maxHeap.toString() + " | " + minHeap.toString() + "중앙 " + String.valueOf(maxHeap.peek()) + "\n");

 

아이디어

ver.1

(1) 최대힙과 최소힙을 선언한다. (PriorityQueue)

(2) 

#CASE 1. minHeap과 maxHeap 사이즈가 같을 때

  CASE 1-1. minHeap의 사이즈가 0일 때

  CASE 1-2. minHeap의 사이즈가 0이 아닐 때 (minHeap,maxHeap 사이즈가 0은 아니지만 같을 때)

      CASE 1-2-1. num이 minHeap.peek()보다 작을 때

      CASE 1-2-2. num이 minHeap.peek()보다 클 때

      CASE 1-2-3. 그 밖에

#CASE 2. minHeap과 maxHeap 사이즈가 다를 때

     CASE 2-1. num이 중앙값보다 작을 때

     CASE 2-2. num이 중앙값보다 크거나 같을 때

 

ver.2

#CASE 1. minHeap과 maxSize가 같을 때

#CASE 2. minHeap과 maxHeap의 사이즈가 다를 때

 

 

추가학습

입력하자마자 값을 확인하겠다고 bw.flush()를 반복문에 넣었더니, 시간초과로 채점되지 않는다.

반복문마다 출력값을 확인할 경우에는 System.out.print()를 사용하자!