[백준] 1655 가운데를 말해요 - JAVA

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

 

1655번: 가운데를 말해요

 

⏰System.out.println()으로 했더니 시간초과가 나서, StringBuilder를 사용했더니 해결되었다. 찾아보니 System.out.println은 내부적으로 동기화방식을 사용하기 때문에 N 최댓값인 100,000개가 주어질 경우 오버헤드가 쌓여 성능저하, 시간초과가 날 수 있다. 

 

 

알고리즘

• 중간값을 기준으로 두개의 우선순위큐를 구현하였다.
• small : 중간값보다 작은 값 , 내림차순 정렬 
• big : 중간값보다 큰 값, 오름차순 정렬 
• N이 홀수개 일경우, 중간값을 기준으로 small 과 big의 크기는 같아야 한다. 
• N이 짝수개 일경우, 중간값을 기준으로 small의 크기가 big 보다 1 작아야 한다.  
• 즉, small의 크기는 big보다 1 작거나, 같아야 한다. 이것을 기억하며 small 과 big, mid값을 조절한다. 

---

 

구현 과정

• small : 현재 중간값보다 작은 값을 담고 있는 우선순위 큐, 값이 클수록 우선순위 ↑ (내림차순 정렬)
• big : 현재 중간값보다 큰 값을 담고 있는 우선순위 큐, 값이 작을수록 우선순위 ↑ (오름차순 정렬) 
• mid : 현재 중간값 

 

1. N개의 수 중 첫번째 수를 mid 값으로 놓고 시작. 

 

2. 남은 N-1개의 수를 입력받으며 아래 과정을 반복한다. 

 

3. 입력받은 수가 현재 mid 값보다 크거나 같을 경우 big 큐에, 작을 경우 small 큐에 add 한다.

 

4. 만약 big의 크기가 small 보다 2만큼 크다면, big 중에 가장 작은값을 mid로 하고, 현재 mid를 small에 add한다. big은 오름차순 정렬되어 있기 때문에 가장 앞의 값을 poll (= big중 가장 작은값) 

 

5. 만약 small의 크기가 big 보다 크다면, small 중 가장 큰 값을 mid로 하고, 현재 mid를 big에 add한다. small은 내림차순 정렬되어 있기 때문에 가장 앞의 값을 poll (= small중 가장 큰 값) 

 

 

👉big이 small 보다 2개 더 많을 경우 

small { 1,2 }

mid 4

big { 6,7,9,11 }

• 현재 mid를 small 에 add 
• mid = big 중 가장 작은 값 

small { 1,2,4 }

mid 6

big { 7,9,11 }

 

 

👉small이 big 보다 많을 경우 

small { 1,2,4 }

mid 6

big { 7,9 }

• 현재 mid를 big에 add 
• mid = small 중 가장 큰 값 

small { 1,2 }

mid 4

big { 6,7,9 }

 

---

 

소스 코드 

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

public class BaekJoon_Solution_1655 {
	public static void main(String[] args) throws Exception {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb= new StringBuilder(); 
		int N= Integer.parseInt(br.readLine()); //정수의 갯수
		
		//중간값보다 더 작은값 (내림차순 정렬)
		PriorityQueue<Integer> small = new PriorityQueue<>((o1,o2)-> o2-o1); 
		//중간값보다 더 큰값 (오름차순 정렬)
		PriorityQueue<Integer> big = new PriorityQueue<>(); 
        
		int mid = Integer.parseInt(br.readLine()); //첫번째 값 mid로 
		while(--N>0) {		
			sb.append(mid).append("\n"); 
			int num = Integer.parseInt(br.readLine()); //입력받은값
			
			//중간값보다 크거나 같을 경우 
			if(mid<=num) big.add(num);
			else small.add(num); 
			
			//하나 스몰로 보내기 
			if(big.size() - small.size() > 1) {
				small.add(mid);
				mid= big.poll();
			}
			
			else if(small.size() > big.size()) {
				big.add(mid);
				mid=small.poll(); 
			}
		}
		sb.append(mid);

		System.out.println(sb);
	}//end of main 
}//end of class