백준 1655번 <가운데를 말해요>

백준 알고리즘 1655번

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

1655번: 가운데를 말해요

---

1655번

입력으로 첫 줄에는 백준이가 외치는 정수의 개수 N이 주어진다.

그리고 그 다음 N개의 줄에 숫자가 들어온다.

 

출력으로는 각 숫자가 들어올 때 들어온 숫자들을 오름차순으로 정렬했을 때 가운데에 있는 숫자를 출력해주면 된다. 

(이때 숫자의 수가 짝수라면 가운데 있는 두 개의 숫자 중 작은 숫자를 출력한다.)

---

문제 해결

우선순위 큐로 문제를 해결하였다.

처음에 파이썬으로 풀었는데 시간초과가 났다! 그래서 자바가 더 빠르지! 이러면서 자바로 풀었다. 

(사실 파이썬으로 풀 때는 우선순위 큐 하나 쓰고 자바로 쓸 때는 우선순위 큐 2개 썼다.)

 

중간 값보다 작은 숫자를 담고 있는 우선순위 큐 small과 중간 값보다 큰 숫자를 담고 있는 우선순위 큐 big 두 개를 사용하였다.

이때 중요한 것은 값을 꺼낼 때 small은 max 값을 꺼내줘야 하고 big은 min 값을 꺼내줘야 한다는 것이다.

자바의 우선순위 큐는 min 값을 꺼내주기 때문에 small에 값을 넣을 때 -를 붙여서 넣어준다.

 

처음 들어온 숫자는 바로 mid가 되고

그 다음에 들어오는 숫자부터는 mid와 비교하여 크면 big에 넣고 작거나 같으면 small에 넣었다.

 

그리고 mid 값을 조정해주는 코드를 추가하였다.

mid 값을 조정해야 하는 경우

1) big의 크기가 (현재까지 들어온 숫자의 개수 / 2)보다 클 경우

2) small의 크기가 (현재까지 들어온 숫자의 개수 / 2)보다 크거나 같고 현재까지 들어온 숫자의 개수가 짝수인 경우

 

1)의 경우에는 big에 숫자가 많은 것이므로 mid를 small에 넣어주고 big에서 하나 꺼내서 mid로 만들어준다.

2)의 경우에는 현재까지 들어온 숫자의 개수가 짝수인데 가운데의 두 숫자 중 큰 숫자가 mid인 경우이다.

따라서 mid를 big에 넣어주고 small에서 하나 꺼내서 mid로 만들어준다.

---

코드

package bj1655;

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

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String str = bf.readLine();
		int testcase = Integer.parseInt(str);
		PriorityQueue<Integer> small = new PriorityQueue<>();
		PriorityQueue<Integer> big = new PriorityQueue<>();
		int mid = 0;
		for (int i = 0; i < testcase; i++) {
			str = bf.readLine();
			int n = Integer.parseInt(str);
			if (i == 0) {
				mid = n;
				bw.write(Integer.toString(mid));
				bw.newLine();
			} else {
				if (n > mid) {
					big.add(n);
				} else {
					small.add((-1) * n);
				}
				if (((i + 1) / 2) < big.size()) {
					small.add((-1) * mid);
					mid = big.poll();
				} else if (((i + 1) / 2) <= small.size()) {
					if ((i + 1) % 2 == 0) {
						big.add(mid);
						mid = (-1) * small.poll();
					}
				}
				bw.write(Integer.toString(mid));
				bw.newLine();
			}
		}
		bw.flush();
		bw.close();

	}

}

 

그리고 가장 중요한 것은,,, BufferedReader와 BufferedWriter를 써야한다는 것이다.

BufferedReader만 사용하고 BufferedWriter를 사용하지 않았을 때 시간 초과가 났다. (출력을 BufferedWriter로 하니까 바로 통과,,)

---

결과

---