알고리즘 풀이(JAVA) - 백준 알고리즘(최대힙, 최소힙)

By on September 18, 2019

문제

문제 링크

풀이

풀이)
이번 문제는 여러 가지로 도전을 하였으나 속도 제한에 걸려서 조금 고민을 하였다. 정렬을 하는 부분에 있어서 힙정렬 퀵정렬을 메소드 등을 이용하여 정렬을 해서 처리하려고 했으나 결국에는 PriorityQueue 자료 구조를 이용해서 처리를 해서 성공을 하였다.

소스

  • 최대힙
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Baekjoon_11279 {
	public static void main(String[] args){
		
        try(BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));){
        	int N = Integer.parseInt(reader.readLine());

        	Queue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
        	
        	for(int i = 0; i < N; i++) {
        		int input = Integer.parseInt(reader.readLine());
        		if(input == 0) {
        			if(queue.isEmpty()){
        				System.out.println(0);
        			}else {
        				System.out.println(queue.poll());
        			}
        		}else {
        			queue.add(input);
        		}
        	}
        }catch(Exception e){
            e.printStackTrace();
        }
    }
}
  • 최소힙
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Baekjoon_1927 {
	public static void main(String[] args){
		
        try(BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));){
        	int N = Integer.parseInt(reader.readLine());

        	Queue<Integer> queue = new PriorityQueue<>(Comparator.naturalOrder());
        	
        	for(int i = 0; i < N; i++) {
        		int input = Integer.parseInt(reader.readLine());
        		if(input == 0) {
        			if(queue.isEmpty()){
        				System.out.println(0);
        			}else {
        				System.out.println(queue.poll());
        			}
        		}else {
        			queue.add(input);
        		}
        	}
        }catch(Exception e){
            e.printStackTrace();
        }
    }
}

Back to blog