백준 1655 자바 - 가운데를 말해요 (BOJ 1655 Java)

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

 

발상이 쉽지 않았다. 시간제한도 짧아서 어떻게 구현할지 좀 막막했음.

일단 0.1초같이 극악한 제한시간이 있는 문제들의 경우 자바로는 아예 통과가 불가한 문제들도 있다.

그래서 일단 채점 현황에 자바로 AC 받은게 있나부터 확인했는데 있어서 자바로 도전함 ㅋㅋ

 

힙을 배열로 어떻게 잘 만들면 O(NlogN)으로 집어넣으면서 바로바로 정렬되고 중간값을 O(1)로 찾을 수 있지 않을까 싶기도 했지만 딱히 구현방식이 생각나지 않았음.

그렇다고 ArrayList에 집어넣고 매번 정렬하는건 당연히 시간초과 날꺼고..

 

그다음으로는 이분탐색쪽을 생각해봤으나 역시 구현할 방법이 딱히 떠오르지 않았음.

그러던 중 보통 이런식으로 2부위나 절반씩 나눠 생각하는 경우 Stack 2개로 왔다갔다

거리는 식으로 해본 기억이 떠올라서 두덩이로 나눠서 생각해봄.

 

그럼 결국 예제에서 나온 1,5,2,10,-99,7,5 를 넣을 때 마다 정렬했다고 치고, 그걸 중간을 똑 뿌러뜨려보자.

이런식으로 [-99, 1, 2, 5] + [5, 7, 10] 으로 나눌 수 있음.

그럼 위에서부터 보자면, 좌측은 내림차순 / 우측은 오름차순이 되고 중간값은 좌측 중 가장 큰 값임.

그럼 필요한걸 정리해봄.

 

1. 넣을 때 바로바로 정렬 될 수 있어야 함. -> 힙 ㄱㄱ

2. 하나는 오름차순, 하나는 내림차순 -> max heap + min heap

3. 두개에 번갈아가면서 값을 넣어야 함. (절반을 유지하기 위해서)

4. 맥스힙에서 가장 큰 값은 항상 민힙의 가장 작은 값보다 작거나 같아야 함.

 

그럼 이걸 위해 코드에서 처리한 부분

 

pq1 : max heap

pq2 : min heap

 

14line, 15line에서 '3'을 처리함.

16line의 조건문에서 '4'를 처리함. pq1의 최대값이 pq2의 최소값보다 큰 상태이므로 서로 교환해주기만 하면 됨. 이 때  일반적으로는 swap에 변수 하나가 필요하지만 이 경우 pq2에서 하나 빼서 pq1에 박아도 pq1의 최대값보다 작으므로 그 아래로 들어가므로 pq1에서 빼는 값에 영향을 안끼침.

 

그럼 매번 숫자를 넣으면서 '3'과 같이 좌우좌우 번갈아 들어가면서, '4'를 만족하는 상태가 유지되므로 매번 max heap에 있는 최대값을 출력해주면 그게 중간 숫자임.

 

https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01600/BOJ_1655.java