[PS] 백준1655: 가운데를 말해요 (Java)

🔗 문제

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

---

📝 풀이

자료 구조 + 우선순위 큐

접근법

입력으로 들어오는 정수들에 대해 기록하고, 중간값을 N번 찾는 문제

입력값 N은 최대 100,000으로 대략적인 시간복잡도는 O(NlogN)으로 잡고 풀어야 한다.

 

단순하게 생각했을 때, 입력을 받으면서 정렬을 계속 수행한 후 현재 개수/2의 인덱스를 구하면 되지만

정렬의 시간복잡도는 O(NlonN)으로 입력값 N에 대해 최대 100,000번 수행한다고 하면 O(N^2)을 넘어서게 된다.

그렇다면 어떻게 풀이를 해야할까?

 

매번 정렬을 수행할 수 없으니 정렬을 유지한 채 값을 기록하고, O(1)로 중간 값을 찾을 수 있어야 한다.

자료구조 중 이러한 특성을 가지고 있는 자료구조가 있다.

기본적인 정렬을 수행하되, 정렬의 시간복잡도가 O(logN)인 우선순위 큐(Priority Queue)를 사용하는 것이다.

 

그러나 한 개의 우선순위 큐만으로는 중간값을 찾는데 오랜 시간이 걸릴 것이다.

왜냐하면 우선순위 큐에는 O(1)로 중간값을 탐색하는 방법이 없기 때문이다.

여기서 약간의 활용이 떠올라야 하는데, 바로 우선순위 큐 두개를 사용해서 현재 정수의 개수의 절반씩 관리하는 것이다.

---

minPQ와 maxPQ 두개로 정렬을 유지한 채 중간값을 O(1)로 탐색

minPQ는 현재 중간값보다 작은 값들을 가지는 우선순위 큐이다.

maxPQ는 현재 중간값을 포함한 큰 값들을 가지는 우선순위 큐이다.

 

여기서 중요한 부분은 maxPQ는 항상 중간값을 포함하고 있어야 한다는 것이다.

그렇기에 maxPQ의 정렬 기준은 오름차순이 되어야한다.

minPQ의 정렬 기준은 어떻게 이루어져야 할까?

입력 정수에 대해 minPQ로 들어가야할지, maxPQ로 들어가야할지를 판단해야 하는데, minPQ에 들어가는 기준은 “중간값보다 낮은 값”이다. 그렇기 때문에 내림차순으로 정렬이 되어 있어야 비교가 가능하다.

 

여기까지 왔다면 입력 정수가 어디에 들어가야할지는 아래와 같이 알 수 있다.

if(maxPQ.peek() > 입력 정수N) minPQ.offer(N);
else maxPQ.offer(N); //maxPQ에 있는 중간값과 동일한 경우에도 삽입해야 함.

그러나 이렇게 추가할 경우 minPQ와 maxPQ의 개수의 차이가 달라져 잘못된 값을 중간값으로 볼 수 있는 경우가 있다.

 

이러한 경우를 피하기위해 우리는 다음과 같은 명제를 생각해야한다.

“maxPQ.peek()는 항상 현재 입력된 정수들의 중간값이 되어야 한다”

“중간값 → 정수의 개수/2”

예로 현재 입력으로 들어온 정수가 4개일 경우(짝수) → minPQ에는 1개, maxPQ에는 3개가 들어가야 한다.

만약 정수가 5개일 경우(홀수)에는 → minPQ에는 2개, maxPQ에는 3개가 들어가야 한다.

maxPQ가 항상 2개 혹은 1개가 더 많아야 하는 이유는 중간값이 maxPQ에 있다는 명제가 있기 때문이다.

 

그러면 아래와 같이 PQ들의 개수를 맞추는 작업이 필요하다는 것을 알 수 있다.

if(minPQ >= maxPQ) maxPQ.offer(minPQ.poll();
else if(minPQ.size()+2 < maxPQ.size()) minPQ.offer(maxPQ.poll();

minPQ는 항상 maxPQ보다 1이상 낮아야 하며, 차이가 3이상 나면 안된다.

즉, minPQ.size() ≥ maxPQ.size()의 경우를 피하기 위해 위와 같은 배치 작업이 이루어져야 한다.

마지막으로 중간값은 항상 maxPQ에 있으니, 매 입력마다 maxPQ의 값을 출력하면 된다.

---

🔎 소스코드

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

//BOJ_1655
public class Main {
    static int N;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        PriorityQueue<Integer> left = new PriorityQueue<>((o1,o2) -> o2-o1);
        PriorityQueue<Integer> right = new PriorityQueue<>();

        StringBuilder sb = new StringBuilder();
        while(N-->0) {
            int idx = Integer.parseInt(br.readLine());

            if(left.isEmpty() && right.isEmpty()) right.offer(idx);
            else {
                if(right.peek() > idx) left.offer(idx);
                else right.offer(idx);
            }

            //size 맞추기 -> right는 항상 left보다 +1
            if(left.size() >= right.size()) right.offer(left.poll());
            else if(left.size()+2 < right.size()) left.offer(right.poll());

            sb.append(right.peek()).append("\\n");
        }

        System.out.println(sb);

    }
}

 

---

💡 정리

코딩테스트를 자주 본 편은 아니지만 몇 번 경험한 느낌으로 이번 문제와 같이 자료구조를 응용하는 문제들이 자주 출제가 되었던 것 같다.

그렇기에 이전에 풀었지만 한번 더 풀면서 정리를 해보았다.

 

두번째 풀이임에도 불구하고, 명제를 세우고 검증을 하는데 조금의 실수가 있었는데

아무래도 세부적인 동작과정을 떠올리는게 부족한 모양이다.

예로 재귀 같은 경우에 호출스택에 따라 결과값을 유추하는 과정을 따라가다보면 현기증이 금방 나버린다…..

 

풀이 후에 다른 사람들의 코드를 보면 몇개의 비교문으로 모든 조건을 만족하는 코드를 작성한 분을 많이 볼 수 있는데, 나의 경우에는 그러한 문제의 조건 및 반례를 커버하는 코드를 작성하는데 있어 개별 조건문으로 스텝을 밟아나가듯 처리하는 습관이 있다.

그렇기에 코드 수가 길어지고, 디버깅 및 검증하는 시간이 오래 걸리게 된다.

 

이러한 문제점을 고칠 수 있는 방법은 아무래도 다른 사람들의 코드를 많이 보아야 하는 것 뿐인가 싶은데, 비슷한 문제에 대해서는 가능하지만 새로운 문제에 대해서는 여전히 부족한 모습을 많이 보이는 것 같다.

 

극복하게 된다면 이에 대해서 추가적인 정리 글을 작성해보고 싶다.