[백준][BOJ-1655][자바] 가운데로 말해요

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		PriorityQueue<Integer> leftMax = new PriorityQueue<>(Collections.reverseOrder());
		PriorityQueue<Integer> rightMin = new PriorityQueue<>();
		
		StringBuilder sb = new StringBuilder();
		
		//맨 처음 값 넣어주기
		leftMax.offer(Integer.parseInt(br.readLine()));
		sb.append(leftMax.peek()+"\n");
		
		for(int i=1; i<N; i++) {
			int num = Integer.parseInt(br.readLine());
			
			//leftMax의  root와 num값 비교
			if(leftMax.peek() >= num) leftMax.offer(num);
			else rightMin.offer(num);
			
			//leftMax와 rightMax 좌우 높이 맞춰주기
			if(leftMax.size() == rightMin.size()+2) {
				rightMin.offer(leftMax.poll());
			}
			else if(leftMax.size()+2 == rightMin.size()) {
				leftMax.offer(rightMin.poll());
			}
			
			// leftMax의 사이즈와 rightMin 사이즈가 틀리다면 큰 쪽이 홀수의 가운데
			// 같다면 짝수에 해당 하기떄문에 leftMax의 peek가 조건에 의한 가운데 수이다.
			if(leftMax.size() >= rightMin.size()) sb.append(leftMax.peek());
			else sb.append(rightMin.peek());
			
			if(i != N-1) sb.append("\n");
		}
		
		System.out.println(sb.toString());
	}
}

정리

이 문제는 매 순간마다 정렬을 한다면 O(n^2) 이 되기 때문에 터진다.

그래서 다른 방향으로 접근해야 되는데 1 2 3 4 5 6 으로 예시로 든다면 반으로 딱 잘랐을 때 {1,2,3}, {4,5,6} 으로 나눌 수 있다. {1,2,3}에서 젤 큰 값이 우리가 구하고자 하는 값이다.

 

1. 먼저 입력 받는 값의 숫자에서 절반으로 잘랐을 때 왼쪽 구역에서 큰 값을 넘겨주는 LeftMax 우선순위 큐와 오른쪽 큰 구역에서 젤 작은 값을 주는 rightMin 우선순위 큐를 선언한다.
2. leftMax의 root 값보다 같거나 작을 때 leftMax에, 아닐떄는 rightMax에 넣어준다.
3. 항상 leftMax과 rightMin은 높이가 맞아야 된다.(그래야 절반의 값이 무엇인지 peek를 통해 확실히 알 수 있다.)
4. 따라서 size가 2이상 차이가 나면 안 되기 때문에 많은 쪽에서 적은 쪽으로 root 값을 넘겨준다.
5. leftMax의 사이즈가 같거나 크다면 leftMax에 가운데 값을 가지고 있기에 sb에 append 한다.

주의사항 

StringBuilder를 사용하지 않고 매 순간마다 print를 한다면 시간 초과가 난다.