[BOJ 백준] 가운데를 말해요(1655) C++, Java

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

1655번: 가운데를 말해요

 

문제 설명 : 

수빈이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 수빈이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 수빈이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

 

출력 : 

 

한 줄에 하나씩 N줄에 걸쳐 수빈이의 동생이 말해야하는 수를 순서대로 출력한다.

 

예제 입력 : 

7
1
5
2
10
-99
7
5

 

예제 출력 : 

1
1
2
2
2
2
5

 

접근법 : 

1) 어떻게 풀 것인가?

N개의 숫자에서 가운데값 (median) 을 알려면 모든 숫자가 정렬된 순서로 있어야한다.

 

그런데 그 숫자가 실시간으로 입력되면서 순서가 바뀐다.

 

실시간 입력된 데이터를 정렬하는 자료구조 = Heap 구조가 있다.

 

힙 구조는 최대힙일경우 가장 위에 값이 최댓값이 되도록 트리를 만드는 구조이고,

최소힙일 경우 가장 위에 값이 최솟값이 되도록 트리를 만드는 구조이다.

 

데이터의 삽입과 삭제시 각각 logN의 시간복잡도가 발생한다.

Java에서는 PriorityQueue 자료형을 통해 쉽게 구현이 가능하고 (아래 코드 참조)

C++ (Cpp)에서는 <queue>를 헤더에 포함시키면 priority_queue로 활용 가능하다.

 

PQ를 이용한다면 현재의 중앙값보다 큰 수가 입력되면 minHeap에 넣고

중앙값보다 작은 수가 입력되면 maxHeap에 넣는방식으로 풀 수 있다.

구체적인 로직은 아래 소스코드 참고

 

참고 : https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

힙 (자료 구조) - 위키백과, 우리 모두의 백과사전

 

 

 

글쓰다가 든 생각인데 이진탐색(binary search)을 변형해 upper_bound 또는 lower_bound를 통해 새로운 값이 입력될 곳을 찾아서 넣고 전체 숫자 개수 나누기 2를 하는 방식으로도 쉽게 찾을 수 있을 것 같다. 

 

2) 시간복잡도

우선순위큐(Priority Queue)의 입출력시 logN의 시간이 발생하므로 2(입력&출력)* N * logN

= 20만 log 20만으로 넉넉하다.

(Java 기준 -  428ms)

 

3) 공간복잡도

수십만개의 int를 PQ에 넣어 100만개 int라고 가정해도 

1,000,000 * int (4Bytes) = 4,000,000 = 3.8 Mbytes 로 여유있다.

 

4) 풀면서 놓쳤던점

특별히 없음

 

5) 이 문제를 통해 얻어갈 것

우선순위큐 (Priority Queue)의 기본적인 활용.

 

C++ 코드 : 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int N;
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N;

    while (N--)
    {
        int x; cin >> x;
        if (maxHeap.size()==0)
            maxHeap.push(x);
        else
        {
            if (maxHeap.size() > minHeap.size())
                minHeap.push(x);
            else
                maxHeap.push(x);
            if (maxHeap.top() > minHeap.top()) 
            {
                int tempMax = maxHeap.top();
                int tempMin = minHeap.top();
                maxHeap.pop();
                minHeap.pop();
                maxHeap.push(tempMin);
                minHeap.push(tempMax);
            }

        }

        cout << maxHeap.top() << "\n";
    }
}

 

Java 코드 : 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.util.PriorityQueue;

// 가운데를 말해요 백준 1655
public class Main {
	
	static int N, input, ans;			// N 숫자 개수, input 입력받는 수, ans 출력할 답
	static int minSize, maxSize, dif;	// 각각 최소힙, 최대힙의 개수, 각 자료구조 개수의 차이
	
	static PriorityQueue<Integer> minHeap;
	static PriorityQueue<Integer> maxHeap;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 최소힙 선언, comparator에서 오름차순정렬
		minHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1 - o2;
			}
		});

		// 최대힙 선언, comparator에서 내림차순정렬
		maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o2 - o1;
			}
		});

		// 최초크기 0으로 선언
		minSize = maxSize = 0;
		
		// N 입력
		N = Integer.parseInt(br.readLine());

		// 첫번째 값은 입력받 값이 곧 답이므로 입력 후 바로 출력하고 ans에 갱신
		ans = Integer.parseInt(br.readLine());
		bw.write(String.valueOf(ans)+"\n");
		// ans를 최대힙에 넣기 (최대힙 : 작은 값들 중에 후보군)
		
		for (int i=2; i<=N; i++) {
			input = Integer.parseInt(br.readLine());
			// 1. input <= ans이면 최대힙에 넣기 (ans보다 작은 값 중에 최댓값이 그나마 다음 후보니까)
			if (input<=ans) {
				maxHeap.offer(input);
				maxSize++;
				
				// 작은값 개수가 1개 이상 많다면 중앙값을 바꿔줌 (짝수개일경우 작은값이 답이므로)
				dif = maxSize - minSize;
				if (dif>=1) {
					minHeap.offer(ans);
					minSize++;
					ans = maxHeap.poll();
					maxSize--;
				}
			}
			// 2. input > ans이면 최소힙에 넣기 (ans보다 큰 값 중 최솟값이 그나마 다음 후보니까)
			else { // if (input>ans) {
				minHeap.offer(input);
				minSize++;
				
				// 큰값이 개수가 2개 이상 많다면 중앙값을 바꿔줌 (짝수개일경우 작은값이 답이므로)
				dif = minSize - maxSize;
				if (dif>=2) {
					maxHeap.offer(ans);
					maxSize++;
					ans = minHeap.poll();
					minSize--;
				}
			}
			// 중앙값 출력
			bw.write(String.valueOf(ans)+"\n");
		}
		
		bw.flush();
		bw.close();
		br.close();
	}
}