백준 11279. 최대힙 (힙, 우선순위큐)

www.acmicpc.net/problem/11279

11279번: 최대 힙

문제제목 : 최대힙

문제난이도 : 실버2

문제유형 : 우선순위 큐

문제

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

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

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

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

코드 (힙 구현)

import java.io.InputStreamReader;
import java.util.ArrayList;
import java.io.BufferedReader;

public class B11279 {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		ArrayList<Integer> output = new ArrayList<>();
		Heap heap = new Heap(n);
		
		for (int i = 0; i < n; i++) {
			int input = Integer.parseInt(br.readLine());
			if (input == 0) {
				output.add(heap.maxPop());
			} else {
				heap.insert(input);
			}
		}
		
		for (int num : output) 
			System.out.println(num);
	}
}

class Heap {
	int[] heap;
	int size;
	int maxSize;
	
	public Heap(int maxSize) {
		size = 0;
		heap = new int[maxSize + 1];
		heap[0] = Integer.MAX_VALUE;
	}
	
	public void insert(int key) {
		int i = ++size;
		while (i != 1 && key > heap[i / 2]) {
			heap[i] = heap[i / 2];
			i /= 2;
		}
		heap[i] = key;
	}
	
	public int maxPop() {
		if (size == 0) return 0;
		
		int max = heap[1];
		
		int temp = heap[size--];

		int parent = 1;
		int child = 2;
		
		while (child <= size) {
			if (child < size && heap[child] < heap[child + 1]) {
				child++;
			} 
			
			if (temp < heap[child]) {
				heap[parent] = heap[child];
				parent = child;
				child *= 2;
			} else {
				break;
			}
		}
		heap[parent] = temp;
		return max;
	}
}

 

코드(우선순위큐)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class PriorityQueueCode {

	public static void main(String[] args) throws Exception {
	
		PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder result = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < n; i++) {
			int input = Integer.parseInt(br.readLine());
			
			if (input == 0) {
				if (queue.size() == 0)
					result.append(0 + "\n");
				else 
					result.append(queue.poll() * -1 + "\n");
			} else {
				queue.add(input * -1); 
				/* 우선순위(1위,2위,3위)는 숫자가 낮은게 우선순위가 높다.
				 * 따라서 최대힙을 구현하기 위해서는 -1을 곱해주고, 제거할때 다시 -1을 곱해줘서 양수로 만든다.
				 */
			}
		}
		System.out.println(result);
	}
}

추가학습

1)

힙을 구현하지않고도 "우선순위 큐"를 이용해서 해결할 수 있다.

PriorityQueue는 우선순위가 가장 높은 것을 먼저 삭제하는 것이다.

PriorityQueue는 특별한 설정없이 사용하면 최소값을 우선으로 삭제한다. (최소값)

최대힙으로 변경하기위핸 따로 해주어야할 것이 필요하다.

 

힙 : 최대/최소값 검색을 위한 구조.

 

2)

StringBuilder :

String객체와 String객체를 더하는 것은 메모리 할당과 메모리 해제를 발생시켜 연산이 많아진다면 성능이 좋지 않다. StringBuilder는 String과 String을 더할때 새로운 객체를 생성하는게 아니라 기존의 데이터에 더하는 방식을 사용해서 속도가 빠르고 부하도 적다.

 

StringBuilder sb = new StringBuilder();
sb.append(a + "\n"); //append() 바로 뒤에 붙이기 때문에, 줄을 바꾸는 출력을 하려면 "\n"을 추가
System.out.println(sb.toString);

 

 

 

 

 

시간복잡도

O(log n)