sm 기술 블로그
185. 1655(가운데를 말해요) - 자바 본문
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 |