BOJ - 1655 가운데를 말해요

1655 가운데를 말해요 : https://www.acmicpc.net/problem/1655

---

Problem

---

Solve

PriorityQueue< Integer > max, PriorityQueue< Integer > min인 2개의 PQ를 가지고 주어진 수의 가운데 값을 구할 수 있다.

예를 들어 1,5,2,10,-99,7,5 라는 수가 주어졌을 때 정렬하게 되면

해당 값과 4번째 자리의 5가 가운데 값이게 된다.

이를 두개의 PQ를 사용하게 되면

max는 내림차순 정렬된 PQ로 max의 최상단은 5가 된다.
min은 오름차순 정렬된 PQ로 min의 최상단은 5가 된다.

이렇게 되면 max의 최상단이 주어진 수의 가운데 값이 되게 된다.

PQ로 구현한 이유는 넣을때 마다 정렬해주기 위해서이다.

이를 토대로 구현해본다면

• max.size() == min.size() 라면 max.offer(num)
• max.size() != min.size() 라면 min.offer(num)

그 후

• max.peek() > min.peek()라면 min값에는 max값보다 큰 값이 있을 수 없기 때문에 두 값을 교환해준다.

이렇게 되면 우선적으로 어떤 수가 들어올 때 두 PQ의 크기에 따라 값이 균형있게 저장이 되며 저장되었을 때 정렬되지 않은 수로 저장이 된다면(max.peek()>min.peek()) 서로의 값을 교환해주어 정렬된 값을 구할 수 있게 되며 주어진 값이 짝수든 홀수든 max.poll()값이 가운데 수가 된다.

예를 들어 7,1,5,2,10,-99,7,5가 주어졌을 때 두 PQ의 상태는 아래와 같게 된다.

---

Code

public class 가운데를말해요 {
	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());

		StringBuilder sb = new StringBuilder();
		//정렬된 배열 중 중간위치의 값 오른편에 있는 값들 오름차순
		PriorityQueue<Integer> min = new PriorityQueue<>();
		//정렬된 배열 중 중간위치를 포함한 왼편에 있는 값들 내림차순
		PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
		for(int i=0;i<N;i++){
			int num = Integer.parseInt(br.readLine());

			if(min.size() == max.size()){
				max.offer(num);
			}else{
				min.offer(num);
			}

			//max의 값이 더 클 때 두 PQ의 값 교환
			if(!min.isEmpty() && !max.isEmpty() && max.peek() > min.peek()){
				int biggerNum = min.poll();
				min.offer(max.poll());
				max.offer(biggerNum);
			}
			sb.append(max.peek());
			sb.append("\n");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}

---

Result

---

Reference

https://loosie.tistory.com/278