BACKJOON/백준 1927 최소힙

문제 : https://www.acmicpc.net/problem/1927

 

관련 알고리즘 : 힙 정렬

 

2021.09.21 - [알고리즘/알고리즘] - 힙 정렬 Heap Sort

 

답안/풀이 JAVA

 

ArrayList 혹은 LinkedList로 풀면 시간초과 발생 

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
			
	public static void main(String[] args) throws IOException {
		
		Main f = new Main();
		
		//화면 입력값 받기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder  sb = new StringBuilder();
		
		Integer length =  Integer.valueOf(br.readLine());
		
		List<Integer> arr = new LinkedList<>();
		
		for(int i = 0; i<length; i++) {
			Integer value = Integer.valueOf(br.readLine());

			if(value > 0) {
				arr.add(value);
				for(int j = arr.size()-1; j>=0; j--) {					
					f.minHeapify(arr, j, 0);
				}
			}else {
				sb.append( (arr.size()>0 ? arr.remove(0) : 0) + "\n");
			}
		}
		System.out.println(sb); 
        br.close();

	}
	
	public void minHeapify(List<Integer>arr, int size, int n) {
		
		int parentIndex = n;
		int leftChildIndex = n*2+1;
		int rightChildIndex = n*2+2;
		
		//왼쪽 자식 노드 확인
		if(leftChildIndex < size) {
			if(arr.get(leftChildIndex) > arr.get(parentIndex)) {
				Collections.swap(arr, leftChildIndex, parentIndex);
			}
			minHeapify(arr, size, leftChildIndex);
		}
		
		//오른쪽 자식 노드 확인
		if(rightChildIndex < size) {
			if(arr.get(leftChildIndex) > arr.get(parentIndex)) {
				Collections.swap(arr, rightChildIndex, parentIndex);
			}
			minHeapify(arr, size, rightChildIndex);
		}
	}
	
}

Collection의 우선순위 큐(PriorityQueue)를 이용해 풀이

* 우선순위 큐 : heap을 이용해 구현된 Queue. (시간복잡도 O(NLogN) ),  높은 우선순위를 가진 요소를 먼저 꺼내어 사용하는 자료구조. 

 

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

public class Main {
			
	public static void main(String[] args) throws IOException {
		
		Main f = new Main();
		
		//화면 입력값 받기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder  sb = new StringBuilder();
		
		Integer length =  Integer.valueOf(br.readLine());
		
		PriorityQueue<Integer> heap = new PriorityQueue<>();
		
		for(int i = 0; i<length; i++) {
			Integer value = Integer.valueOf(br.readLine());
			
			if(value > 0) {
				heap.add(value);
			}else {
				sb.append( heap.size() > 0 ? heap.poll() : 0);
				sb.append("\n");
			}
		}
		System.out.println(sb); 
        br.close();

	}
	
}