[BOJ - JAVA] 1655 - 가운데를 말해요 (우선순위 큐)

# 주소

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

1655번: 가운데를 말해요

# 문제

# 문제 해설 및 코드 리뷰

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

public class Main {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(x -> x));
        PriorityQueue<Integer> q = new PriorityQueue<>((o1,o2)->o2-o1);
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++){
            int x = Integer.parseInt(br.readLine());
            if(queue.size() == q.size())
                q.offer(x);
            else
                queue.offer(x);
            if(!queue.isEmpty() && !q.isEmpty()){
                if(queue.peek() < q.peek()){
                    int now = queue.poll();
                    queue.offer(q.poll());
                    q.offer(now);
                }
            }
            sb.append(q.peek() + "\n");
        }
        System.out.println(sb);
    }
}

난이도가 확실히 있었습니다.

Queue를 이용해서 푸는데, 인덱스의 중간값을 찾으라니 생각보다 접근하기 어려웠습니다.

LinkedList의 경우엔 index를 찾아서 해당 인덱스를 경우마다 출력하면 되지만 Queue의 경우엔 선입선출구조이기 때문에 배열의 특정 인덱스 값을 찾아서 꺼내는 것은 할 수 없습니다.

다라서 다른 분들의 코드를 참고해야 했습니다.

원래는 한 개의 PriorityQueue와 Deque을 같이 써서 해보려 했는데 그렇게 하게 되면 시간복잡도가 O(N^2)이 걸리기 때문에 상당히 비효율적이고 시간초과도 나길래 결국 찾아보았습니다.

다른 분들의 풀이는 굉장히 신박하고 배울 것이 많았기 때문에 참고할만한 가치가 있었기에 포스팅합니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(x -> x));
PriorityQueue<Integer> q = new PriorityQueue<>((o1,o2)->o2-o1);
StringBuilder sb = new StringBuilder();

일단 전 N값이 크기 때문에 Buffer를 사용했습니다.

그리고 최댓값부터 정렬하는 PriorityQueue와 최댓값부터 정렬하는 PriorityQueue를 선언했습니다.

또한 StringBuilder을 사용하는데, System.out.println이 시간초과가 나면 이 방법을 쓰도록 합니다..

for(int i = 0; i < n; i++){
    int x = Integer.parseInt(br.readLine());
    if(queue.size() == q.size())
        q.offer(x);
    else
        queue.offer(x);
    if(!queue.isEmpty() && !q.isEmpty()){
        if(queue.peek() < q.peek()){
            int now = queue.poll();
            queue.offer(q.poll());
            q.offer(now);
        }
    }
    sb.append(q.peek() + "\n");

for문을 이용해서 일단 x를 입력받습니다.

그리고 queue와 q를 번갈아가면서 입력을 받습니다.

if(!queue.isEmpty() && !q.isEmpty()){
    if(queue.peek() < q.peek()){
        int now = queue.poll();
        queue.offer(q.poll());
        q.offer(now);
    }
}

이후 queue와 q가 비어있지 않을 때에 queue의 peek가 q의 peek보다 작다면 queue에서 점을 하나 빼와서 그걸 now에 담고 q에 담습니다.

그리고 q에서도 점을 하나 빼와서 queue에 넣습니다.

그럼 제가 원하는 가장 이상적인 모습은 queue에는 최솟값부터 정렬되면서 q보다 모두 큰 수가 들어가고 q에는 queue보다 모두 작으면서 최댓값부터 정렬된다면 

예)

queue = [4,5,6]

q = [3,2,1]

이렇게 정렬된다면 queue의 제일 앞에 있는 값, q의 제일 앞에 있는 값 중 q를 sb에 담으면 되는 것입니다.

이 구조로 만들기 위해선 만약 queue의 값보다 q가 더 클 경우 queue와 q의 원소를 각각 교체해주어 중앙값을 찾는 것이 목표입니다.

단번에 이해하기 어려울 것이라 생각듭니다. 그래서 더더욱 연습이 필요한 것 같습니다.

q의 최댓값과 queue의 최솟값을 비교하는데, 궁극적으로 위의 예제처럼 queue의 원소가 q의 원소보다 크면 안되기 때문에 교체해주어서 최종적으로 queue와 q를 가르는 것이 목표가 되겠습니다.

예제를 넣어보면서 이해해볼까요?

7
1
5
2
10
-99
7
5

이 예제를 넣었을 때 queue와 q는 어떻게 출력되어야 할까요?

queue 는 [5, 10, 7] 이렇게 나오고

q는 [5, 2, -99, 1]이렇게 나오는 것을 확인할 수 있습니다.

어라? 자동정렬인데 왜 이렇게 나올까요? 자동정렬 되어서 queue와 q가 나와야 하는 것 아닌가요?

네 맞습니다. 하지만 그걸 이해하려면 이 힙의 형태에 대해 먼저 이해할 필요가 있습니다.

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

[자료구조] 힙(heap)이란 - Heee's Development Blog

힙의 정의는 우선순위 큐(PriorityQueue)를 정의하기 위해 등장한 개념입니다.

최대힙, 최소힙에서 우선순위 큐를 구할 때 오름차순으로 쭉 정렬하고 내림차순으로 쭉 정렬한다고 이해했다면 그것은 틀린 개념입니다.

무슨 말이냐면, 이 우선순위큐는 우선적으로 가치가 가장 높은 원소를 출력하는 것이 목표이기 때문에 이 큐에서 가장 우선순위가 높은 원소를 제일 인덱스의 앞단에 두고 이것이 빠져나갈 때 까지 기다립니다.

그럼 이 원소가 만약 빠져나가게 된다면 그 때 새로 정렬을 통해 새로운 원소를 우선순위가 가장 높은 원소로 두는 것입니다.

출력을 순서대로 하면 당연히 오름차순, 또는 내림차순이 되겠지만 queue와 q의 동작 방식을 제대로 이해하고 있다면 알고리즘 우선순위큐를 이해하는데 큰 무리 없을 것이라 생각듭니다.

다들 저 포스팅 꼭 한 번씩 보시길 바랄게요.