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

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

문제 요약

정수가 주어지면 지금까지 주어진 정수 중에 중간값을 말해야 한다.
다만 짝수 개가 주어졌다면 중간의 두 수 중에 더 작은 값을 말한다.
주어지는 정수는 최대 10만개, 각 정수의 값은 절대값 1만 이하이다.

---

문제 접근

우선순위 큐를 2개 사용하면 된다. (정수 N개 훑으면서 힙에 넣기 빼기를 하기 때문에 전체는 NlogN)
flag를 두고 왼쪽 큐, 오른쪽 큐에 순서대로 넣는다.
왼쪽 큐는 큰 수 우선(내림차순), 오른쪽 큐는 작은 수 우선(오름차순)으로 만든다.
넣은 뒤에 왼쪽 큐와 오른쪽 큐의 가장 앞의 값을 서로 비교해서 왼쪽 큐의 값이 더 크면 교체한다.
그리고 왼쪽 큐의 가장 앞의 값을 출력하면 된다.
이를 각 입력 정수에 대해 반복한다.

---

풀이

기본적인 아이디어는 다음과 같다.

1. (정리 예정)

이를 구현한 코드는 다음과 같다.

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		// 정의할 것: 입력 개수 N, 우선순위 큐 2개, 입출력 할 것들, 좌우 판단용 flag
		int N;
		
		PriorityQueue<Integer> leftQueue = new PriorityQueue<>(Collections.reverseOrder());
		PriorityQueue<Integer> rightQueue = new PriorityQueue<>();
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		// true면 왼쪽, false면 오른쪽에 넣기
		boolean flag = true;
		
		// 입력 개수 N 받기
		N = Integer.parseInt(br.readLine());
		
		// 입력을 받으면서 중간값을 출력에 추가
		for (int i = 0; i < N; i++) {
			int num = Integer.parseInt(br.readLine());
			
			// flag에 따라 해당 큐에 넣기
			if (flag) {
				leftQueue.add(num);
			} else {
				rightQueue.add(num);
			}
			
			// 처음에 오른쪽 큐가 비어있을 때는 넘어가야함
			if (rightQueue.size() < 1) {
				sb.append(leftQueue.peek()+"\n");
				flag = !flag;
				continue;
			}
			
			// 좌우 큐의 값을 비교해서 역전되었다면 교체
			int leftHead = leftQueue.peek();
			int rightHead = rightQueue.peek();
			
			if (leftHead > rightHead) {
				int temp = rightQueue.poll();
				rightQueue.add(leftQueue.poll());
				leftQueue.add(temp);
			}
			
			// 왼쪽 큐에서 현재의 중간값 얻어서 기록
			int mid = leftQueue.peek();
			sb.append(mid+"\n");
			
			flag = !flag;
		}
		
		// 결과 출력
		System.out.println(sb);
	}
}

---

회고

(추가 예정)