백준 [N2696 - 중앙값구하기]

 

풀이방법 : 무식하게 푸는 방법과 우선순위큐를 활용해 푸는 방법이 있다

 

무식하게 푼 소스코드이다.

주석으로 풀이과정을 간단히 설명해보았다. 핵심은 리스트로 입력값을 받을 때마다 정렬하여 중앙값을 get해준다는 것이다.

public class Main {
    private static List<Integer> list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());//테스트케이스의 수
        StringTokenizer st = null;
        for(int i=0;i<t;i++){
            StringBuilder sb = new StringBuilder();
            int n = Integer.parseInt(br.readLine());
            bw.write((n/2+1)+"\n");//첫째 줄에 출력하는 중앙값의 개수
            list = new ArrayList<>();//입력받을 때마다 정렬하여 중앙값 구하는 용도
            int cnt = 0;//한 줄에 10개씩 출력하기 위한 용도
            for(int j=0;j<n;j++){
                if(j%10==0) st = new StringTokenizer(br.readLine());//입력 값이 10개 넘어가면 다음 줄에서 입력받는다.
                list.add(Integer.parseInt(st.nextToken()));
                if(j%2==0) {//홀수 번째 수(인덱스로는 짝수가 된다)를 읽을 때마다
                   cnt++;//출력 개수를 +1해주고
                   if(cnt%10==0) sb.append(center()+"\n");//한 줄에 출력개수가 10개가 넘으면 다음줄로 넘어간다
                   else sb.append(center()+" ");
                }
            }
            bw.write(sb.toString().trim()+"\n");
        }
        br.close();
        bw.flush();
        bw.close();
    }

    private static int center() {
        Collections.sort(list);//홀수 번째 수를 읽을 때마다 정렬하여
        return list.get(list.size()/2);//중앙값을 구한다
    }
}

 

 

우선순위큐를 활용해 푼 소스코드이다.

위와 큰 차이점은 정렬을 위해 리스트를 활용한 것과 달리 우선순위큐를 활용했고 center()메서드에서 그 차이가 보인다.
입력받은 수만큼 우선순위큐 크기가 달라지는데, 그 (크기/2 +1) 만큼 poll하면 중앙값을 구할 수 있고 poll값들을 stack에 넣어 다시 우선순위큐에 넣어주어야 한다.

하지만, 이렇게 우선순위큐와 스택을 사용해 값을 넣다 빼는 것은 비효율적이며 무식하게 푼 것보다 더 많은 메모리와 시간을 차지하게 된다. 

비효율적이라 생각해 다른사람의 풀이를 확인해보고 아..! 최대힙과 최소힙을 같이 활용하면 된다는 것을 깨달았다.

아래는 최소힙과 스택을 사용해 푼 소스코드이다.

public class Main {
    private static PriorityQueue<Integer> pq;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        StringTokenizer st = null;
        for(int i=0;i<t;i++){
            StringBuilder sb = new StringBuilder();
            int n = Integer.parseInt(br.readLine());
            bw.write((n/2+1)+"\n");
            int cnt = 0;
            pq = new PriorityQueue<>();
            for(int j=0;j<n;j++){
                if(j%10==0) st = new StringTokenizer(br.readLine());
                pq.add(Integer.parseInt(st.nextToken()));
                if(j%2==0) {
                   cnt++;
                   if(cnt%10==0) sb.append(center()+"\n");
                   else sb.append(center()+" ");
                }
            }
            bw.write(sb.toString().trim()+"\n");
        }
        br.close();
        bw.flush();
        bw.close();
    }
    
    public static int center(){
        Stack<Integer> stack = new Stack<>();
        int size = pq.size();
        for(int i=0;i<=size/2;i++){
            stack.push(pq.poll());
        }
        int center = stack.peek();
        while(!stack.isEmpty()){
            pq.add(stack.pop());
        }
        return center;
    }
}

 

 

최대힙과 최소힙을 사용해 코드를 아래와 같이 수정해보았다.

풀이과정

STEP1. 최대힙과 최소힙의 크기가 같은 경우, 최대힙에 입력값을 넣어준다. 같지 않은 경우는 최소힙에 입력값을 넣는다.
(최대힙과 최소힙에 1개씩 번갈아 가며 넣어준다는 의미이다.)

STEP2. 최소힙이 비어있지 않을 경우, 최대힙과 최소힙의 Peek값을 비교해 최대힚 peek값이 더 클 경우 peek값을 서로 바꿔준다.
(최소 2개이상의 입력값을 받아야 최대힙과 최소힙의 peek값을 비교할 수 있기 때문에 최소힙이 비어있지 않은지 확인하는 것이다.)

이 과정을 거치면 최대힙의 peek값은 항상 중앙값이 놓이게 된다.

public class Main {
    private static PriorityQueue<Integer> maxHeap;
    private static PriorityQueue<Integer> minHeap;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        StringTokenizer st = null;
        for(int i=0;i<t;i++){
            StringBuilder sb = new StringBuilder();
            int n = Integer.parseInt(br.readLine());
            bw.write((n/2+1)+"\n");
            int cnt = 0;
            maxHeap = new PriorityQueue<>((o1,o2)->o2-o1);
            minHeap = new PriorityQueue<>();
            for(int j=0;j<n;j++){
                if(j%10==0) st = new StringTokenizer(br.readLine());
                addHeap(Integer.parseInt(st.nextToken()));
                if(j%2==0) {
                    cnt++;
                    if(cnt%10==0) sb.append(maxHeap.peek()+"\n");
                    else sb.append(maxHeap.peek()+" ");
                }
            }
            bw.write(sb.toString().trim()+"\n");
        }
        br.close();
        bw.flush();
        bw.close();
    }

    private static void addHeap(int x) {
        if(minHeap.size()== maxHeap.size()) maxHeap.add(x);
        else minHeap.add(x);

        if(!minHeap.isEmpty()) {
            if (maxHeap.peek() > minHeap.peek()) {
                minHeap.add(maxHeap.poll());
                maxHeap.add(minHeap.poll());
            }
        }
    }
}