[백준] 1655 가운데를 말해요 - 우선순위큐(PriorityQueue) + 아이디어 + 시간초과 JAVA

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

1655번: 가운데를 말해요

코드설명

우선순위큐 2개를 활용하는 문제입니다.

 

문제를 간단하게 보면, Arrays.sort() 를 활용하여 각 길이의 절반의 위치를 비교하여 진행하는 방법이 있습니다.

하지만, 시간복잡도를 보면 Arays.sort()의 시간복잡도는 O(n Log n) 이고, N번을 진행하므로 O(N * N log N) 이므로 시간초과가 납니다.

 

그렇기에, 우선순위큐 2개를 활용하여 진행합니다.

maxPQ는 내림차순으로 정렬하고, (즉, 가장 큰값이 맨위)

minPQ는 오름차순으로 정렬합니다. (즉, 가장 작은값이 맨위)

 

문제 로직입니다.

1. 만약 maxPQ와 minPQ의 사이즈가 같다면, maxPQ에 값을 넣습니다.

2. 만약 사이즈가 maxPQ가 더 커진다면, minPQ에 값을 넣습니다.

위의 과정을 통해 항상 둘의 사이즈가 1이상 차이나지 않게 처리합니다.

 

3. 만약 maxPQ의 최대값이 minPQ의 최소값 보다 크다면, maxPQ와 minPQ의 값을 변경하여 maxPQ에서 minPQ로 증가하는 양상을 나타나게 처리합니다.

위의 과정을 통해 항상 외친 수의 개수가 짝수개라면 중간에 있는 두수 중에서 가장 작은 수를 말해야한다는 조건을 충족시키고, 값을 올바르게 정렬할 수 있습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.regex.Pattern;

public class Main {
	public static int N, K;
	public static String str;
	public static int[][] arr;
	public static StringBuilder sb = new StringBuilder();
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	PriorityQueue<Integer> maxPQ = new PriorityQueue<>((o1, o2) -> o2 - o1); //내림차순
    	PriorityQueue<Integer> minPQ = new PriorityQueue<>((o1, o2) -> o1 - o2 ); //오름차순
    	
    	for(int i=0; i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		int num = Integer.parseInt(st.nextToken());
    		if(maxPQ.size() == minPQ.size()) maxPQ.add(num);
    		else minPQ.add(num);
    		
    		// maxPQ가 더 클경우 원소를 바꿔줍니다.
    		if(!maxPQ.isEmpty() && !minPQ.isEmpty()) {
    			if(maxPQ.peek() > minPQ.peek()) {
    				int temp = maxPQ.poll();
    				maxPQ.offer(minPQ.poll());
    				minPQ.offer(temp);
    			}
    		}
    		sb.append(maxPQ.peek()).append("\n");
    		
    	}
    	
    	System.out.println(sb);
    	
    }
    
    
}