sm 기술 블로그

185. 1655(가운데를 말해요) - 자바 본문

문제/백준_자바

185. 1655(가운데를 말해요) - 자바

sm_hope 2022. 8. 23. 19:43
import java.util.*;
import java.io.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		PriorityQueue<Integer> leftQue = new PriorityQueue<>();
		PriorityQueue<Integer> rightQue = new PriorityQueue<>();

		for (int i = 0; i < N; i++) {
			int x = sc.nextInt();

			if (leftQue.size() == rightQue.size()) leftQue.add(-x);
			else rightQue.add(x);
			
			if(!rightQue.isEmpty() && (rightQue.peek() < -leftQue.peek())) {
				int rightValue = rightQue.remove();
				int leftValue = -leftQue.remove();
				
				rightQue.add(leftValue);
				leftQue.add(-rightValue);
			}
			
			sb.append(-leftQue.peek()).append("\n");
		}
		
		System.out.print(sb);
	}
}

문제요약

값이 들어올 때 마다 오름차순으로 했을 경우 중앙값을 구하라 (만약 짝수면 두개의 중앙값 중 작은거 출력)

설명

먼저 단순히 생각을 하면 아래의 순서로 진행될 것이다.

이를 구현하기 위해 정렬을 계속 이용한다면 시간초과가 발생할 것이다.

따라서 힙 큐(우선순위 큐)를 이용한다.

힙 큐는 트리형태 여서 아무생각 없이 중앙을 출력 한다면 오류가 발생한다.

예를들어 50 10 20 을 큐에 저장하면 큐는 10 50 20 형태를 갖추고 있다.

하지만 heappop (우선순위 큐에서는 get) 을 통해 세번 출력을 한다면 10 20 50 으로 정상적으로 오름차순의 형태를 나타낼 것이다.

 

그러면 어떻게 가운데를 푸느냐?? 두개의  힙 큐를 이용한다.

다음과 같이 준비하여 왼쪽 힙은 중앙 값보다 작은 값, 오른쪽 힙은 중앙 값보다 큰값을 넣는다.

 

(1) 1 입력

왼쪽은 내림차순으로 정렬해야한다. (중앙값이 0번째 인덱스로 오기 위해서)

그러면 -를 붙여 힙에 입력하면 된다.

 

왼쪽과 오른쪽의 길이가 같은 경우에는 왼쪽에 집어 넣는다.

 

(2) 5 입력

왼쪽 힙과 오른 쪽 힙의 길이가 같지 않을 경우에는 먼저 오른쪽 힙에 집어 넣는다.

그 후 왼쪽의 0번째 값과 오른쪽의 0번째 값을 비교한다 (이 둘이 짝수일 경우의 중앙 값)

※ 왼쪽 힙은 -를 붙여 주었기 때문에 -를 붙여 비교한다.

 

만약, 왼쪽값이 오른쪽 값보다 크다면 두개의 위치를 서로 바꿔준다.

 

(3) 2 입력

다시말하지만 왼쪽은 0번째 값이 가장 큰 값이 되어야 하므로 내림차순으로 정렬한다. (맨 위가 중앙값)

 

(1)번과 마찬가지로 길이가 같은 경우이기 때문에 왼쪽 힙에 값을 넣는다.

 

그 후, 오른쪽에 값이 있을 경우 (2)번의 과정을 진행한다. (왼쪽에 0번째 값과 오른쪽의 0번째 값을 비교하는 과정)

 

(4) 10 입력

이후는 똑같은 과정이므로 그림만 보여주도록 하겠다.

 

(5) -99 입력

(6) 7 입력

(7) 5 입력

이미 존재하는 5가 입력 되었다.

하지만 우리는 왼쪽과 오른쪽 힙의 길이를 통해서 값을 넣는 과정을 진행하기 때문에 크게 문제 되지 않는다.

 

위 과정과 똑같이 왼쪽, 오른쪽의 길이가 같으므로 우선  왼쪽 힙에 저장을 한다.(내림차순을 위해 -를 붙이고)

왼쪽의 0번째 5와 오른쪽 0번째 5를 비교했을 때 둘은 같기 때문에 자리이동은 필요 없으며 마지막 결과의 중앙값은 5가 된다.

'문제 > 백준_자바' 카테고리의 다른 글

187. 11049(행렬 곱셈 순서) - 자바  (0) 2022.08.27
186. 11066(파일 합치기) - 자바  (0) 2022.08.25
184. 11286(절댓값 힙) - 자바  (0) 2022.08.22
183. 1927(최소 힙) - 자바  (0) 2022.08.22
182. 11279(최대 힙) - 자바  (0) 2022.08.21
Comments