[Baekjoon] 2696_중앙값 구하기

Gold II

문제(출처: https://www.acmicpc.net/problem/2696)

---

< 중앙값 구하기 >

 

문제 풀이 

 

백준 1655번 문제와 매우 비슷한 문제이다. 

https://melody-coding.tistory.com/342

[Baekjoon] 1655_가운데를 말해요

 

1655번 문제와 다른 점은 홀수번째 수를 읽을 때마다 중앙값을 출력하는 것이며, 테스트 케이스가 주어진다는 것이다.

 

 

 my solution (Java)

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

public class _2696_ { // 중앙값 구하기

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int t = Integer.parseInt(bf.readLine());

		PriorityQueue<Integer> left = new PriorityQueue<>(Collections.reverseOrder());
		PriorityQueue<Integer> right = new PriorityQueue<>();

		for (int i = 0; i < t; i++) {
			int m = Integer.parseInt(bf.readLine());

			bw.write(Integer.toString(m / 2 + 1) + "\n");
			int idx = 0;
			for (int j = 0; j < (m / 10 + 1); j++) {
				st = new StringTokenizer(bf.readLine());

				while (st.hasMoreTokens()) {
					int num = Integer.parseInt(st.nextToken());
					idx += 1;

					if (left.size() == 0)
						left.add(num);
					else {
						if ((right.size() > 0 && right.peek() >= num) || left.peek() > num) {
							left.add(num);
						} else {
							right.add(num);
						}

						if (left.size() - right.size() > 1) {
							int temp = left.poll();
							right.add(temp);
						} else if (right.size() - left.size() > 1) {
							int temp = right.poll();
							left.add(temp);
						}
					}

					if (idx % 2 == 1) {
						if (left.size() > right.size()) {
							bw.write(Integer.toString(left.peek()) + " ");
						} else {
							bw.write(Integer.toString(right.peek()) + " ");
						}
						if ((idx / 2 + 1) % 10 == 0)
							bw.write("\n");
					}
				}
			}

			bw.append("\n");
			left.clear();
			right.clear();
		}
		bw.flush();
	}
}

 

Main

변수)
t : 테스트 케이스 개수
left : 내림차순 우선순위 큐
right : 오름차순 우선순위 큐
m : 수열의 크기
idx : 현재까지 읽은 원소 수
num : 수열의 원소

 

- 테스트 케이스의 개수(t) 입력

- 테스트 케이스 수만큼 수열의 크기와 수열 입력

- 수열의 크기(m)를 이용해서 중앙값의 개수를 구함

: (m / 2 ) + 1

- 원소가 10개씩 나누어져서 입력되므로 [수열의 크기(m)/10 +1] 만큼 반복해서 원소 입력

1) left 우선순위 큐가 비어있다면 left 우선순위 큐에 num 추가

2) right 우선순위 큐에 값이 있으면서 맨 앞에 있는 값보다 작거나 left 우선순위 큐의 맨 앞에 있는 값보다 작으면 left 우선순위 큐에 num 추가

3) 2)에 해당하는 경우가 아니라면(= right 우선순위 큐의 맨 앞에 있는 값보다 크면) right 우선순위 큐에 num 추가

4) 중간 값을 찾는 것이므로 left 우선순위 큐와 right 우선순위 큐의 size를 보고 size가 같거나 1 차이 나도록 수정

5) 결과 출력

: 현재까지 정수를 홀수개 외쳤다면 left와 right 우선순위 큐 중에서 size가 큰 우선순위 큐의 맨 앞에 있는 값을 출력

---

---