JAVA 백준 2696 중앙값 구하기 (우선순위 큐)

 

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

---

문제

1. 첫째 줄에 테스트 케이스의 개수 T (1 <= T <= 1000) 이 주어진다.
2. 각 테스트 케이스의 첫째 줄에 수열의 크기 M (1 <= M <= 9999, M % 2 == 1) 이 주어진다.
3. 그 다음 줄부터 수열의 원소가 공백으로 구분되어 입력된다. 이 때 원소는 한 줄에 10개씩으로 나누어져 입력된다.
4. 각 테스트 케이스에 대해 첫째 줄에 출력하는 중앙값의 개수를 출력하고, 둘째 줄에는 홀수 번째 수를 읽을 때마다 중앙값을 공백으로 구분하여 출력. (한 줄에 10개씩)

---

 

 

 

ArrayList로 푼 최종 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < T; i++) {
            int M = Integer.parseInt(br.readLine());
            int num = (M + 1) / 2;

            ArrayList<Integer> list = new ArrayList<>();

            sb.append(num).append("\n");

            int lines = M / 10;
            if (M % 10 != 0) {
                lines++;
            }

            int index = 0;
            for (int j = 0; j < lines; j++) {
                if (j != 0 && index % 10 == 0) {
                    sb.append("\n");
                }
                StringTokenizer st = new StringTokenizer(br.readLine());

                while (st.hasMoreTokens()) {
                    list.add(Integer.parseInt(st.nextToken()));
                    if (list.size() % 2 == 1) {
                        Collections.sort(list);
                        sb.append(list.get(index++)).append(" ");
                    }
                }
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }
}

 

우선순위 큐인 거 모르고 풀어서 시간초과 나겠다 싶었는데 맞아서 조금 황당했다.

 

일단 코드 설명을 하자면 중앙값의 개수는 ( M + 1 ) / 2 개이다.

홀수일 때마다 출력하므로 절반만큼의 횟수를 출력한다.

 

ArrayList에 원소를 추가하고 ArrayList의 크기가 홀수가 될 때마다 ArrayList를 정렬하고 중앙값을 출력하도록 한다.

나는 이 때 중앙값을 따로 구하지 않고 인덱스를 담는 변수를 추가하여 출력값을 구해 결과에 더할 때마다 인덱스의 값을 증가시키도록 했다.

두 개의 수를 더할 때 중앙에 위치한 값은 1씩 더해지기에 가능한 방법이다.

원소가 한 줄에 10개가 되면 다음 줄로 넘어갈 수 있도록 한다.

 

우선순위 큐로 푼 최종 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < T; i++) {
            int M = Integer.parseInt(br.readLine());

            PriorityQueue<Integer> maxQueue = new PriorityQueue<>();
            PriorityQueue<Integer> minQueue = new PriorityQueue<>(Comparator.reverseOrder());

            sb.append((M + 1) / 2).append("\n");
            int index = 0;

            int lines = M / 10;
            if (M % 10 != 0) {
                lines++;
            }

            for (int j = 0; j < lines; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());

                while (st.hasMoreTokens()) {
                    if (minQueue.size() == maxQueue.size()) {
                        maxQueue.offer(Integer.parseInt(st.nextToken()));
                    } else {
                        minQueue.offer(Integer.parseInt(st.nextToken()));
                    }

                    if (!minQueue.isEmpty() && !maxQueue.isEmpty()) {
                        if (minQueue.peek() > maxQueue.peek()) {
                            minQueue.add(maxQueue.poll());
                            maxQueue.add(minQueue.poll());
                        }
                    }
                    index++;

                    if (index % 2 == 1) {
                        sb.append(maxQueue.peek()).append(" ");
                    }
                    if (index % 20 == 0) {
                        sb.append("\n");
                    }
                }
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

 

중앙값을 기준으로 maxQueue와 minQueue로 나누어 중앙값이 맨 앞으로 올 수 있도록 하였다.

두 큐 중 하나는 Comparator.reverseOrder()로 내림차순 정렬하여 이용한다.

 

두 큐의 맨 앞의 수를 비교했을 때 minQueue 쪽의 수가 더 크다면 두 수의 front에 있는 수를 서로 교환할 수 있도록 하여 중앙값이 될 수 있도록 만든다.

 

 

비교하여보니 시간 차이가 생각보다 많이 난다.

 

아래가 ArrayList를 이용한 코드고 위가 PriorityQueue를 사용한 코드이다.

메모리나 시간 차이가 꽤 많이 나는 것을 볼 수 있다.

우선순위 큐를 이용하는 이유가 있는 것 같다.