스파르타 알고리즘 트랙 문제 5일차 - 2 #11279 최대 힙

문제

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

해결 과정

힙 자료구조를 구현하여 해결하는 문제이다.

힙은 이진 트리 구조로 형성되어 부모 노드의 값이 자식 노드의 값보다 무조건 큰, 혹은 작은 형태의 자료구조이다. 따라서 힙을 구현한 후, 그 자료구조에 1의 경우는 값을 집어넣는 메소드를, 2의 경우는 값을 빼는 메소드를 작성하면 될 것으로 보인다.

 

Java에서는 PriorityQueue라는 이미 힙 형태로 만들어진 자료구조 클래스가 존재하여 이를 사용하여 문제를 해결해 보았다.

import java.io.*; import java.util.*; public class Main {     public static void main(String[] args) throws IOException {         Scanner sc = new Scanner(System.in);         int N = sc.nextInt();         PriorityQueue<Integer> arr = new PriorityQueue<>(Collections.reverseOrder());         while(N!=0){             int num = sc.nextInt();             if (num==0) {                 System.out.println(arr.size()==0?0:arr.remove());             }             else  {                 arr.add(num);             }             N--;         }     } }

입력받은 숫자가 0일 경우, 힙의 크기가 0일 경우 0을, 크기가 0이 아닐 경우 데이터를 빼온 후 출력하고, 그 외의 경우에는 힙에 저장하는 형태로 코드를 구성하였다.

 

이미 만들어진 class와 메소드를 사용하여 크게 어렵지 않은 문제였으나, LinkedList 형태의 이진 트리 클래스를 직접 만들어 해결해 보는 것도 좋을 듯하다.