[JAVA] 백준 1655번 【G2.가운데를 말해요】

문제

1655번: 가운데를 말해요

 

---

풀이

1️⃣ 우선 순위 큐 두개를 활용한 풀이

💡 떠오른 Idea

우선 순위 큐는 이진 힙 방식으로 구성되어 있기 때문에, 사용하면 정렬을 유지한 삽입 과정을 O(logN) 에 수행할 수 있다.

그리고, 우선 순위 큐에 따라 정렬된 데이터를 꺼낼 때 역시, O(logN) 로 수행할 수 있다.

따라서 우선 순위 큐를 사용하는게 시간 복잡도를 만족시킬 수 있다고 판단하였다.


가운데 수를 항상 말해야 하므로,

내림차순으로 정렬된 우선순위 큐 (left) 와 오름차순으로 정렬된 우선 순위 큐(right) 2개를 활용한다.

left 에는 지금까지 백준이가 외친 수의 개수 중 내림차순으로 절반을 넣을 것이고 

right 에는 나머지 수들을 오름차순으로 넣을 것이다.

그리고 매번 left 의 peek() 했을 때 나온 수를 반환하면 된다.

백준이가 수를 외쳤을 때

1. left 큐가 비어있는 경우 
  → left 큐에 일단 삽입한다. 이유는 원소가 한개일 때, left 의 peek 한 값이 가운데 값이 된다.

2. 그 외, 경우
 → 백준이가 부른 수가 left 큐의 최댓값보다 작으면 left 큐에 넣고 크다면 right 큐에 넣는다.

3. 백준이가 수를 부르고 나서 2번 과에 따라 큐에 집어넣은 후
→ left 큐의 크기가 right 큐의 크기 +1 이상으로 바꿔준다.

ex) left = [ 3 ] , right = [  ]  , 부른 수 =  2

→ left = [ 2, 3 ] , right = [ ] 

→ 3번 과정 거치기

→ left = [ 2 ] , right = [ 3 ]

4. 위 과정을 거치고 left 의 peek 값을 반환하면 가운데 값이 된다.

 

 

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));

        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> left = new PriorityQueue<>((a, b) -> b - a);
        PriorityQueue<Integer> right = new PriorityQueue<>();

        StringBuilder ans = new StringBuilder();

        while (N-- > 0) {
            int n = Integer.parseInt(br.readLine());
			
            // left 큐가 비어있으면 left 큐에 추가
            if (left.isEmpty()) {
                left.offer(n);
            } else {
                Integer maxOfLeft = left.peek();
				
                // left 큐의 최댓값보다 작으면 left 큐에 추가
                if (maxOfLeft >= n) {
                    left.offer(n);
                // left 큐의 최댓값보다 크면 right 큐에 추가    
                } else {
                    right.offer(n);
                }
            }
			
            // left 큐와 right 큐 재배치
            arrangeQueueSize(left, right);

            ans.append(left.peek() + "\n");
        }

        System.out.println(ans);
    }

    private static void arrangeQueueSize(PriorityQueue<Integer> left, PriorityQueue<Integer> right) {
        int sizeOfLeft = left.size();
        int sizeOfRight = right.size();

		// 왼쪽 큐 보다 오른쪽 큐가 더 큰 경우, 왼쪽 큐로 이동
        if (sizeOfLeft < sizeOfRight) {
            left.offer(right.poll());
        } else {
        	// 왼쪽 큐가 오른쪽 큐 크기 + 1 보다 큰경우 오른쪽 큐로 이동
            if (sizeOfLeft > sizeOfRight + 1) {
                right.offer(left.poll());
            }
        }
    }
}

 

 

결과

 

논리를 잘 세우고 그에 맞춰 구현을 했더니 잘 해결할 수 있었던 것 같다.