[백준] 2696 중앙 값 구하기 java

배열로 무식하게 푸는 방법과 우선순위 큐를 이용해서 푸는 2가지 방법이 있었다.

 

첫번째로는 배열을 사용한 풀이인데 나는 우선 이것부터 떠올렸다. 매번 값을 받을 때 마다 sort를 해주어서 홀수번 째 마다 중앙값을 구해주면 됐는데 시간초과가 날줄 알았지만 간당간당하게 통과했다. 아무래도 수열의 크기가 크지 않아서 그랬던 듯 하다.

 

두번째 풀이는 min-heap과 max-heap을 이용한 풀이였다. 이건 다른 분들의 블로그를 참고해서 푼 문제이다. 확실히 배열로 풀었을 때 보다 최적화 면에서 더 나았다. 어떻게 이걸 바로 떠올리고 풀지라는 신기한 생각을 또 가지게 되었다. (__)

 

1. 중앙값의 개수 출력  => (N+1) / 2

2. 최대힙과 최소힙의 크기가 같다면 최대힙, 다르다면 최소힙에 값을 넣는다.

3. 최대힙은 항상 중앙값 이하의 값들만 가지고 있어야 하기 때문에 최소힙이 비어있지 않다면 최댓값과 최솟값을 비교해서 최소값의 크기가 더 작다면 서로 값을 스위칭 해준다.

4. 홀수번 째 값일 경우 최대힙에 있는 값을 peek한 후 출력해준다.

 

 

배열을 이용한 풀이

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

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int T, N;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        input();
        solve();
        System.out.print(sb);
    }

    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        sb = new StringBuilder();
    }

    static void solve() throws IOException{
        for(int i = 0; i < T; i++) {
            int mid = 0;
            N = Integer.parseInt(br.readLine());
            if(N % 2 == 0)sb.append(N/2).append("\n");
            else sb.append(N/2+1).append("\n");
            List<Integer> arr = new ArrayList<>();

            int k = N / 10;
            if(N <= 10) k = 1;
            int standard = (k > 1)? 10 : N;
            while(k-- > 0) {
                st = new StringTokenizer(br.readLine());
                for(int j = 1; j <= standard; j++) {
                    arr.add(Integer.parseInt(st.nextToken()));

                    if(j % 2 != 0) {
                        Collections.sort(arr);
                        sb.append(arr.get(mid++)).append(" ");
                        if(mid % 10 == 0) sb.append("\n");
                    }
                }
            }
            if(standard != 10) sb.append("\n");
            if(N > 10 && N % 10 != 0) {
                st = new StringTokenizer(br.readLine());
                for(int j = (N/10)*10+1; j <= N; j++) {
                    arr.add(Integer.parseInt(st.nextToken()));

                    if(j % 2 != 0) {
                        Collections.sort(arr);
                        sb.append(arr.get(mid++)).append(" ");
                    }
                }
            }
        }
    }
}

우선순위 큐를 사용한 풀이

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

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb;
    static int T;

    public static void main(String[] args) throws IOException {
        init();
        solve();
        System.out.print(sb);
    }

    static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        T = Integer.parseInt(br.readLine());
    }

    static void solve() throws IOException{
        while(T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            int cnt = 0;
            PriorityQueue<Integer> min = new PriorityQueue<>();
            PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());

            // 1. 중앙값의 개수 출력
            sb.append(((N+1) / 2) + "\n");

            for(int i = 0; i < N; i++) {
                if(i % 10 == 0) {
                    st = new StringTokenizer(br.readLine());
                }

                // 2. 최대힙과 최소힙의 사이즈가 같다면 최대힙, 다르다면 최소힙에 넣는다.
                int val = Integer.parseInt(st.nextToken());
                if(max.size() == min.size()) {
                    max.add(val);
                } else {
                    min.add(val);
                }

                // 3. 최소힙에서 peek한 값과 최대힙에서 peek한 값보다 작을 경우 스위칭 해준다.
                //최대힙은 중앙값 이하의 값들만 가져야 성립하기 때문이다.
                if(!min.isEmpty()) {
                    if(min.peek() < max.peek()) {
                        int minVal = min.poll();
                        int maxVal = max.poll();

                        min.add(maxVal);
                        max.add(minVal);
                    }
                }

                // 4. 홀수번 째 마다 max.peek 값 출력 (여기선 0부터 시작이니 짝수번 째)
                if(i % 2 == 0) {
                    //10개 째면 끊어주어야 함.
                    if(cnt == 9 || i == N - 1) {
                        sb.append(max.peek() + "\n");
                        cnt = 0;
                    } else {
                        sb.append(max.peek() + " ");
                    }
                    cnt++;
                }
            }
        }
    }
}