백준 11279번 최대 힙 [Heap] :: 마이구미

이번 글은 백준 알고리즘 사이트 11279번 '최대 힙' 문제를 알아볼 것이다.

자료구조 중 힙 에 관한 문제이다.

Github - https://github.com/hotehrud/acmicpc

힙은 트리를 기반으로 된 자료구조다.

일단 이것만 기억하면 된다.

힙은 완전 이진 트리이다.

이진트리는 자식노드가 최대 2개인 트리이지 않느냐?

또한 균형이 잡혀있는 트리이다.

힙은 최대 힙과 최소 힙으로 나눌 수 있다.

아래 그림처럼 최대 힙은 부모 노드가 자식 노드보다 큰 값을 가지는 구조이다.

최소 힙은 당연히 반대이다.

당연히 힙으로 푼다.

혹시 이전 글 10814번 나이순 정렬 글을 보면 좋다.

http://mygumi.tistory.com/44

이번에도 우선순위 큐로 문제를 해결할 것이다.

나는 그냥 최대 힙을 구현해서 풀었지만...

다른 사람이 푼 소스를 보고.... 아 훨씬 좋네... 

깨달음을 얻었다.. 다시 한번 우선순위 큐로 풀어보자! 

이번 기회에 확실히 잡아놓자.

여기서 왜 우선순위 큐로 푸는 것이냐..?

궁금증이 나올 수 있다.

이론상으로도 힙은 우선순위 큐를 구현하는 데 많이 이용한다.

또한! 우리가 저번 문제에서도 그랬듯 이번 문제에서도 쓸 우선순위 큐!
자바에서 제공하는 우선순위 큐 클래스.

이 녀석은 힙 기반으로 만들어졌다.

이 문제는 최대 힙을 필요로 하기 때문에 지난 번처럼 오버라이딩을 했다.

compare 메소드를 오버라이딩하여 최대 힙으로 만들어주었다.

10814번과 11279번을 PriorityQueue로 풀어보자.

그렇다면 충분히 응용할 수 있을만큼 자기 것이 될 것이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PriorityQueue<Integer> arr = new PriorityQueue<Integer>(new ComparatorDescending());
		
		int nc = Integer.parseInt(br.readLine());
		while (nc-- > 0) {
			int t = Integer.parseInt(br.readLine());
			if (t == 0) {
				if (arr.peek() != null) {
					System.out.println(arr.poll());
				} else {
					System.out.println(0);
				}
			} else {
				arr.add(t);
			}
		}
	}
}

class ComparatorDescending implements Comparator<Integer>
{
	@Override
	public int compare(Integer n1, Integer n2) {
		// TODO Auto-generated method stub
		if (n1 < n2) {
            return 1;
        } else {
            return -1;
        }
	}
}

최대 힙을 구현해서 푸는 것 또한 많이 도움될 것이다.

참고 자료

http://algorithms.tutorialhorizon.com/priority-queue-implementation/