[백준] 1655 가운데를 말해요 - Java / Python

 

 

 

시간 제한을 보고 당연히 배열로 푸는건 시간 초과가 걸릴것 같아 ArrayList로 접근했다.

 

그런데 ArrayList도 시간 초과가 나온다..

 

다른 분들의 풀이를 보고 겨우 이해했다.

 

문제에서 의미하는 중앙값을 뽑아내기 위해 하나는 최대 힙, 하나는 최소 힙으로 두 가지의 우선순위 큐를 선언한다. 

 

최대 힙부터 시작해서 하나씩 숫자를 넣어 주는데, 최대 힙의 루트 노드값이 최소 힙의 루트 노드값보다 크면 두 노드값을 바꿔줘야 하고, 입력에 대해서는 최대 힙의 루트 노드값을 출력해 주면 된다.

 

이런 생각은 어떻게 하는지.. 수능 수학을 공부할 때 참신한 발상이 필요한 30번 문제를 보는 것 같다..

 

"중앙값을 빠르게 구할 때 두 가지 우선순위 큐를 만들어서 구하는 방법이 있다" 정도만 기억해 두고, 주기적으로 복습해서 잊어버리지 않도록 해야겠다.

 

Java

 

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

public class Main {

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

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

		PriorityQueue<Integer> min = new PriorityQueue<>();
		PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());

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

			if(min.size() == max.size()){
				max.add(command);
			}else{
				min.add(command);
			}

			if(min.isEmpty()==false && max.isEmpty() == false){
				if(min.peek() < max.peek()){
					int temp = min.poll();
					min.add(max.poll());
					max.add(temp);
				}
				
			}
			sb.append(max.peek()).append('\n');
		}

		System.out.println(sb);



	}
}

 

 

Python

 

파이썬도 자바와 같은 방향으로 풀 수 있다.

 

다만, 최대 힙을 구현할 때 튜플을 사용하는 방법 대신 -1을 곱한 값을 넣어주는 방법을 사용했다.

 

import heapq
import sys

N = int(input())
maxheap = []
minheap = []


for i in range(N):
    command = int(sys.stdin.readline())
    if(len(minheap) == len(maxheap)):
        heapq.heappush(maxheap, -command)
    else:
        heapq.heappush(minheap, command)
    
    if(minheap and maxheap):
        if(maxheap[0]*-1 > minheap[0]):
            temp = heapq.heappop(minheap) 
            heapq.heappush(minheap, heapq.heappop(maxheap)*-1)
            heapq.heappush(maxheap, temp*-1)
    print(maxheap[0]*-1)