[Algorithm] 백준 1655번(BOJ 1655) 가운데를 말해요 (Java)

---

안녕하세요 coding-knowjam입니다.

오늘은 백준 온라인 저지에 있는 1655번 가운데를 말해요 문제를 풀어보겠습니다.

문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다.

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

 

1. 문제 설명

문제에서 요구하는 바는 숫자가 하나씩 추가가 될 때, 현재까지 나온 숫자들 중에서 중간값을 출력하면 됩니다.

숫자의 개수가 홀수면 중간값이 1개이고, 짝수인 경우는 중간값이 없기 때문에 중간에 있는 두 수중에서 작은 수를 출력하면 됩니다.

문제를 해결하기 위한 가장 간단한 방법은 정수가 추가될 때마다 배열을 정렬해서 중간에 있는 값을 출력하는 것입니다. 그러나 이러한 방식으로 접근을 하게 되면 시간 초과 판정을 받게 됩니다. 문제에서 요구하는 시간은 0.1초 내에 푸는 것이고 이를 위해서는 N * logN의 시간 복잡도가 아닌 logN의 시간 복잡도를 가지도록 구현해야 합니다.

시간 내에 문제를 풀기 위해서는 우선 정수가 추가되면, 자동으로 정렬이 되도록 하는 것이 중요합니다. 이를 위해 우선순위 큐(Priority Queue)를 사용할 수 있습니다. 우선순위 큐는 내부적으로 Heap 자료구조를 사용하며 정렬 기준에 따라 최대 힙, 최소 힙으로 사용할 수 있습니다.

우선순위 큐를 사용해서 정수의 개수가 홀수번째일 때는 최대 힙에, 짝수일 때는 최소 힙에 정수를 추가해줍니다. 이러한 과정에서 최대 힙의 root값이 최소 힙의 root값보다 큰 경우에는 각각의 힙에서 root값을 꺼내서 교환해줍니다. 이후에는 최대 힙에 있는 root값이 중간값이 되므로 이를 출력하면 됩니다.

이렇게 정렬이 자동으로 될 수 있는 것은 heap자료구조의 특성입니다. heap의 경우 최대 힙, 최소 힙으로 분류되며 완전 이진트리의 형태를 띠고 있습니다. heap은 새로운 값이 추가되면 내부적으로 heapify라는 정렬 작업을 수행해서 root노드의 값이 항상 최대 또는 최소의 값을 가질 수 있도록 유지합니다.

heap에 대해서는 나중에 다루기로 하고 궁금하신 분은 개인적으로 학습해보시길 권해드립니다.

그럼 코드를 살펴보겠습니다.

 

2. Java로 문제 풀이

package study.blog.codingknowjam.algorithm.boj;

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

public class BOJ_1655 {
	private static PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());        // 최대힙
	private static PriorityQueue<Integer> minHeap = new PriorityQueue<>();                                // 최소힙

	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 N = Integer.parseInt(br.readLine());

		// 정수의 개수만큼 하나씩 정수를 가져온다.
		for (int i = 1; i <= N; i++) {
			// 정수 가져옴
			int number = Integer.valueOf(br.readLine());
			// 힙에 넣기
			offerHeap(i, number);
			// 최대힙 최소힙 비교해서 스왑
			ifMaxHeapGreaterThanMinHeapSwap();
			// 중간 값 추출
			bw.write(String.valueOf(maxHeap.peek()));
			bw.newLine();
		}
		// 출력
		bw.flush();
	}

	/**
	 * 최대힙의 root값이 최소힙의 root값보다 크면 root값을 교환한다.
	 */
	private static void ifMaxHeapGreaterThanMinHeapSwap() {
		// 최대힙의 root가 최소힙의 root보다 크면
		if (isMaxHeapGreaterThanMinHeap()) {
			// 힙에서 root값을 빼서 교환
			int maxHeapRoot = maxHeap.poll();
			int minHeapRoot = minHeap.poll();
			maxHeap.offer(minHeapRoot);
			minHeap.offer(maxHeapRoot);
		}
	}

	/**
	 * 최대힙과 최소힙에 노드가 존재하고, 최대힙의 root가 최소힙의 root보다 큰지 판단
	 * @return true:최대힙의 root값이 크다, false:최소힙의 root값이 크거나 같다.
	 */
	private static boolean isMaxHeapGreaterThanMinHeap() {
		return !maxHeap.isEmpty() && !minHeap.isEmpty() && maxHeap.peek() > minHeap.peek();
	}

	/**
	 * 힙에 정수를 넣는다
	 * 홀수면 최대힙에, 짝수면 최소힙에 추가
	 * @param totalNumberOfInteger : 현재까지 정수의 총 개수
	 * @param number			   : 힙에 추가 할 정수
	 */
	private static void offerHeap(int totalNumberOfInteger, int number) {
		if (oddCheck(totalNumberOfInteger)) { // true : odd, false: even
			maxHeap.offer(number);
			return;
		}
		minHeap.offer(number);
	}

	/**
	 * 홀수인지 아닌지 체크한다.
	 * @param totalNumberOfInteger : 현재까지 정수의 총 개수
	 * @return true:홀수, false:짝수
	 */
	private static boolean oddCheck(int totalNumberOfInteger) {
		return totalNumberOfInteger % 2 != 0;
	}
}

주석과 코드를 같이 살펴보시면 이해하는데 크게 어렵지 않으실 겁니다.

감사합니다.

---