[Java] BOJ1655, 백준 - 가운데를 말해요

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

1655번: 가운데를 말해요

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
0.1 초	128MB	22427	6500	5004	31.547%

문제

수빈이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 수빈이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 수빈이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

 

출력

한 줄에 하나씩 N줄에 걸쳐 수빈이의 동생이 말해야하는 수를 순서대로 출력한다.

 

 

<풀이>

시간 제한이 0.1초이다.

N의 최댓값은 100,000이기 때문에 2중for문을 쓴다던지 하면 안된다.

그래서 한 번의 탐색으로만 찾을 수 있는 방법을 찾아보았다.

for문 한번만 돌리면 무조건 가능하기 때문 > 우선순위 큐

 

입력되는 수 중에서 중간값을 갖는 수를 찾아야한다. (짝수일 경우에는 가운데의 두 수 중 더 작은 수)

우선순위 큐를 두 개 만들어서, 중간값부터 두 번째 큐에, 중간값보다 작은 숫자들은 첫 번째 큐에 넣어준다.

그러면 출력할 때는 pq2의 peek값을 출력해주면 된다.

 

예제를 기준으로 예시를 들어보면 다음과 같다.

입력: N=7 / 1 5 2 10 -99 7 5 순으로 주어진다고 하자.

 

i	입력	pq1	pq2
0	1		1
1	5		1 5
2	2	1	2 5
3	10	1	2 5 10
4	-99	-99 1	2 5 10
5	7	-99 1	2 5 7 10
6	5	-99 1 2	5 5 7 10

 

그러면 큐 안에 담긴 원소들은 i값이 변함에 따라서 위와 같이 변할것이다.

여기서 한 가지 규칙을 발견할 수 있다.

i%2 == 0일때는 정확히 중간에 있는 값을 찾아야하고,

i%2 == 1일때는 가운데 두 개중 더 작은 것을 찾아야 하기 때문에

i%2==0일때는 pq1에 원소를 추가해줘야하고, i%2==1일때는 pq2에 원소를 추가해줘야한다.(i==0일때 제외)

 

대신 넣을 때 크기만 비교해주면 된다.

pq2에 원소를 넣으려고 하는데, pq1에 있는 원소들 중에서 최댓값보다 작다면 서로 바꿔줘야겠죵?

 

코드로 구현할 때는 순서만 바꿔서

1. 넣으려는 원소의 크기를 비교해서 일단 pq2에 넣는다.
2. i가 홀수인지 짝수인지에 따라서 pq2에 넣은 원소를 pq1으로 옮겨준다.

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		// 입력부
		int n = Integer.parseInt(br.readLine());
		// pq1이 상대적으로 더 작은 수
		// pq2의 peek값을 출력해준다.
		PriorityQueue<Integer> pq1 = new PriorityQueue<Integer>(Collections.reverseOrder());
		PriorityQueue<Integer> pq2 = new PriorityQueue<Integer>();

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

			// 만약 pq1에서 가장 큰 수보다 작은 수가 입력된다면
			// 교체해준다
			if (pq1.size() > 0 && tmp < pq1.peek()) {
				pq2.add(pq1.poll());
				pq1.add(tmp);
			} else {
				pq2.add(tmp);
			}

			if (i != 0 && i % 2 == 0) {
				// i%2 == 0일때는 딱 가운데에 있는 숫자를 찾아야함(총 숫자가 홀수개)
				// i%2 == 1일때는 더 작은것을 찾아야하기 때문에, pq1로 옮겨주지 않고 pq2의 peek값을 출력해주면 된다
				pq1.add(pq2.poll());
			}

			sb.append(pq2.peek() + "\n");
		}
		System.out.println(sb);
	}
}