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

Gold II

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

---

< 가운데를 말해요 >

 

문제 풀이 

 

우선순위 큐 2개(left: 내림차순, right: 오름차순)를 사용해서 문제를 해결했다.

 

처음에는 left에 값을 넣어준다. 그다음 값을 보고 left queue의 맨 앞에 있는 값 보다 작은 값이라면 left queue에 넣어준다. 만약 right queue의 맨 앞에 있는 값 보다 크다면 right queue에 넣어준다.

가운데 값을 찾는 것이므로 값을 넣을 때마다 left와 right queue의 size 차이가 2 이상 난다면 1 차이 또는 같도록 맞춰준다.

 

문제에 주어진 예시대로 1, 5, 2, 10, -99, 7, 5가 들어온다고 가정해 보자. 아래와 같이 표현되도록 구현했다.

왼쪽: 내림차순 우선순위 큐/오른쪽: 오름차순 우선순위 큐

 

 

 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;

public class _1655_ { // 가운데를 말해요

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

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

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

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

			if (left.size() < 1) {
				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 ((i + 1) % 2 == 0) {
				bw.write(Integer.toString(left.peek()) + "\n");
			} else {
				if (left.size() > right.size())
					bw.write(Integer.toString(left.peek()) + "\n");
				else
					bw.write(Integer.toString(right.peek()) + "\n");
			}
		}
		bw.flush();
	}
}

 

Main

변수)
n : 정수의 개수
left : 내림차순 우선순위 큐
right : 오름차순 우선순위 큐
num : 외치는 정수

 

- 외치는 정수의 개수(n) 입력

- 정수의 개수만큼 반복하여 외치는 정수(num) 입력

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

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

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

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

5) 결과 출력
: 현재까지 정수를 짝수개 외쳤다면 두 수 중에서 작은 수를 말해야 하므로 left 우선순위 큐의 맨 앞에 있는 값을 출력

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

---

---