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

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

1655번: 가운데를 말해요

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {
    static int num;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        PriorityQueue<Integer> right = new PriorityQueue<>();
        PriorityQueue<Integer> left = new PriorityQueue<>(Collections.reverseOrder());
        
        int N = Integer.parseInt(br.readLine());
        
        for (int i = 1; i <= N; i++) {
            num = Integer.parseInt(br.readLine());
            
            if(left.isEmpty())
                left.add(num);
            else if (right.isEmpty()) {
                right.add(num);
                if (left.peek() > right.peek()) {
                    left.add(right.poll());
                    right.add(left.poll());
                }
            }
            else if (num > right.peek())
                right.add(num);
            else
                left.add(num);
                
            //총 짝수개면서 균형 안 맞는 경우
            if (i % 2 == 0 && left.size() != right.size()) {
                if (left.size() < right.size())
                    left.add(right.poll());
                else right.add(left.poll());
            }
            //홀수개면서 오른쪽에 붙은 경우
            if (i % 2 == 1) {
                while (left.size() <= right.size())
                    left.add(right.poll());
            }
            
            sb.append(left.peek()).append("\n");
        }
        System.out.print(sb);
    }
}

💡 우선순위 큐

풀이

💬 처음엔 이분탐색으로 시도했는데 실패ㅎㅎ.. 시간초과 이슈

 

- 1 2 5 10 중 중간수를 출력하기 위해 반을 나누면 ... 1, 2 // 5, 10 으로 생각할 수 있다.

➡️ 이것을 각각 왼쪽 파트, 오른쪽 파트를 담당하는 우선순위 큐로 구현할 수 있다.

• 왼쪽 영역을 나타내는 우선순위 큐는 내림차순, 오른쪽 영역을 나타내는 우선순위 큐는 오름차순으로 나타냄
• 중간 수를 출력할 때 무조건 왼쪽 큐(내림차순)에서 peek 해서 출력한다고 가정하자
  • 짝수일 때 두 수중 작은 수를 말해야 함
  • 홀수일 경우 left.size() > right.size() 여야 함 (1개 차이)

for(i-> 1 ~ N)
	//처음 2개는 각각 하나씩 할당하고 시작
    if(left.isEmpty)
    	left.add(num)
    else if(right.isEmpty)
    	right.add(num)
        //왼> 오인 경우 바꿔줌
        if(left.peek() > right.peek())
        	left.add(right.poll())
            right(left.poll())
    //오른쪽 최솟값보다 큰 경우 -> 오른쪽으로 들어감
    else if(num > right.peek())
    	right.add(num)
    else
    	left.add(num)
    //짝수 & 양쪽 균형 안맞는경우--> 같게 조정
    if(i % 2 == 0 && left.size() != right)
    	left.add(right.poll()) OR right.add(left.poll())
    //i가 홀수인 경우 => num이 right가서 붙은 경우 옮겨줘야 함
    while(left.size() <= right.size()){
    	left.add(right.poll())
     
    //출력
    sb.append(left.peek())