알고리즘 풀이(JAVA) - 백준 알고리즘(가운데를 말해요)

By on September 24, 2019

문제

문제 링크 : (가운데를 말해요) https://www.acmicpc.net/problem/1655

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

예를 들어 수빈이가 동생에게 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줄에 걸쳐 수빈이의 동생이 말해야하는 수를 순서대로 출력한다.

풀이

  • 중간값을 기준으로 중간값 보다 작은 값을 저장 하는 min 큐와 큰값을 저장하는 max 큐를 선언
  • 입력 되는 값을 max 큐에 넣는다(오름차순)
  • 조건
    • 전체 숫자의 수 (min.size() + max.size())가 짝수 가 아닐 경우 max의 최우선값(가장작은수) 를 min에 넣는다.
    • 전체 숫자의 수 (min.size() + max.size())가 짝수 일 경우 min의 최우선값(가장큰수)이 입력된 숫자 보다 클경 우 서로 자리를 바꾼다.
  • min의 최우선값을 출력한다(min의 최우선값은 항상 중간숫자로 유지된다)

소스

  • 가운데를 말해요.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Baekjoon_1655 {
	public static void main(String[] args) {
		Queue<Integer> max = new PriorityQueue<>();
		Queue<Integer> min = new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o2.compareTo(o1);
			}
		});
		
		try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));) {
			int N = Integer.parseInt(reader.readLine());

			for (int i = 0; i < N; i++) {
				int num = Integer.parseInt(reader.readLine());
				max.add(num);
				if( !isEvenSize(max, min) ) {
					min.add(max.poll());
				}else if(min.peek() > num) {
					max.add(min.poll());
					min.add(max.poll());
				}
				System.out.println(min.peek());
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	private static boolean isEvenSize(Queue<Integer> max, Queue<Integer> min) {
		return (min.size() + max.size()) % 2 == 0;
	}
}

Back to blog