백준 2696 자바 - 중앙값 구하기 (BOJ 2696 JAVA)

문제 : https://www.acmicpc.net/problem/2696

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02600/BOJ_2696.java

 

1. 중앙값을 빨리 찾기 위한 방식을 찾아야 한다. 이렇게 중앙값을 취하는 경우 보통 절반씩 나눠서 어떠한 자료구조에 넣는 방식으로 풀면 괜찮은 경우가 많다.

 

2. 이 문제의 경우 힙 2개에 넣으면 괜찮게 풀 수 있다. PriorityQueue 2개를 둬보자. 하나는 맥스힙, 하나는 민힙으로 사용한다. 예를들어 1,2,3,4,5,6,7,8,9가 맥스힙에 1,2,3,4,5가 들어있고, 6,7,8,9가 민힙에 들어있다고 보자. 맥스힙에서 하나를 peek해보면 가장 큰 수인 '5'가 나올테고, 민힙에서 하나를 peek해보면 가장 작은 수인 '6'이 나올 것이다. 그럼 항상 맥스힙과 민힙의 개수가 같거나, 맥스힙이 1개가 더 많도록 유지한다면 무조건 맥스힙에서 peek한 값이 중앙값이 될 것임을 알 수 있다.

 

3. 그럼 하나하나 입력 받으면서 어떻게 맥스힙과 민힙에 넣을지 규칙만 잘 정하면 된다. 일단 홀수번째 수는 항상 맥스힙에 넣는다. 짝수번째 수는 항상 민힙에 넣는다. 일단 이렇게 하면 항상 맥스힙의 개수가 민힙의 개수보다 같거나 1개 더 많게 할 수 있다.

 

4. 또 하나 중요한 점은, 맥스힙의 모든 값은 민힙의 모든 값 보다 작아야 한다는 점이다. 이걸 유지하려면 매번 입력받은 후에 맥스힙의 peek 값이 민힙의 peek값보다 크다면 맥스힙에서 가장 큰 값과 민힙에서 가장 작은 값을 swap 해주면 된다.

 

위 규칙만 지켜서 입력을 받으면 쉽게 중앙값을 구할 수 있다.

코드에서 맥스힙은 pq1, 민힙은 pq2로 나타냈다.

홀수번째는 맥스힙에, 짝수번재는 민힙에 넣는 부분은 17~18line이다.

서로 값을 비교해 swap해주는 부분은 19~22line이다.

출력시 10개마다 줄을 변경해줘야 하는 부분도 수행해야한다. 이 부분은 코드에서 24line이다.