백준 1655 / 최대힙(MaxHeap), 최소힙(MinHeap) / JAVA

오늘 살펴볼 문제는 백준 1655번 <가운데로 말해요> 문제이다.

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

1655번: 가운데를 말해요

나는 처음에 이 문제를 정말 단순하게 직관적으로 접근했었다.

N개의 입력값을 받아서 하나씩 ArrayList에 받고 그 때마다 정렬을 한 뒤 i/2 번째 원소를 찾아서 출력하면 되지 않나?

라고 접근해서 풀었고 시간초과가 나왔다. 이는 당연한게 시간 복잡도가 O(N*N*logN)이 나오는데 N = 100,000 이기 때문이다. (참고로 ArrayList의 sort() 알고리즘은 시간복잡도가 NlogN이다.)

그래서 접근 방법을 바꾸어서 힙(Heap)을 사용했다. 나는 최대힙과 최소힙을 각각 하나씩 사용했다.

먼저 왼쪽에 최대 힙이 있고 오른쪽에 최소 힙이 있다고 가정하자. 입력값을 하나씩 받을 때 마다 왼쪽 최대힙, 오른쪽 최소힙에 한 번씩 번갈아 가면서 넣어 주도록 한다. 그렇게 될 경우 가운데에 있는 숫자는 왼쪽 최대힙의 root 값임을 알 수 있다.

첫 번째 숫자를 왼쪽에 넣었으니 두 번째 숫자를 오른쪽에 넣어야 한다. 그런데 이 때부터는 왼쪽 최대힙의 root값과 오른쪽 최소힙의 root값을 비교해서 왼쪽이 오른쪽보다 크면 swap을 한다. 문제에서 준 예제에서는 이런 경우가 없었다.

이 과정을 계속해서 반복한다. 계속해서 반복해도 가운데 값은 항상 왼쪽 최대힙의 root값임을 알 수 있다.

이렇게 해서 문제를 풀면 시간복잡도 O(N*logN) 으로 깔끔하게 맞출 수 있다. 자바에서는 PriorityQueue 클래스가 Heap 자료구조를 제공해 주어서 직접 구현하지 않고 import 해서 사용하였다.

아래는 내가 제출한 자바 소스코드이다.

 

힙의 구조에 대해서 생각하며 풀 수 있는 좋은 문제이다. 추천추천 ㅎㅎ