[알고리즘] 우선순위 큐 문제 풀이(백준 1927번, 11279번)

1. 최소 힙(백준 1927번)

 

1927번: 최소 힙 (acmicpc.net)

1927번: 최소 힙

 

▷ 풀이 코드

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

public class MinHip {
	
	public static void main(String args[]) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int num = Integer.parseInt(br.readLine());
		
        PriorityQueue<Integer> minQueue = new PriorityQueue<Integer>();

		
		for(int i=0; i<num; i++) {
			
			int input = Integer.parseInt(br.readLine());
			
			if(input == 0) {
				if(minQueue.size() <= 0) sb.append("0").append("\n");
				else {
					sb.append(minQueue.poll()).append("\n");
				}
			}else {minQueue.add(input);}
			
			
		}
		System.out.println(sb);

	}
}

 

 

2. 최대 힙(백준 11279번 문제)

 

11279번: 최대 힙 (acmicpc.net)

11279번: 최대 힙

 

▷ 풀이 코드

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

public class Main {
	
	public static void main(String args[]) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int num = Integer.parseInt(br.readLine());
		
        PriorityQueue<Integer> maxQueue = new PriorityQueue<Integer>(Collections.reverseOrder());

		
		for(int i=0; i<num; i++) {
			
			int input = Integer.parseInt(br.readLine());
			
			if(input == 0) {
				if(maxQueue.size() <= 0) sb.append("0").append("\n");
				else {
					sb.append(maxQueue.poll()).append("\n");
				}
			}else {maxQueue.add(input);}
			
		}
		System.out.println(sb);

	}
}

 

 

이번에는 알고리즘 스터디를 통해 배운 큐를 통해 백준 문제 풀이를 해보았습니다!!

 

큐는 FIFO 구조이지만 우선 순위 Queue를 이용하면 해당 값이 출력되고 난 후 최솟값이 우선순위로 출력되도록 바뀌네요!

 

또한, Collections.reverseOrder를 사용하면 역순으로 최댓값이 우선순위로 출력되네요!!

 

Queue를 이용하니 Array, List, Map을 이용한 것보다 훨씬 더 빠르게 수행되는 것을 확인할 수 있어요

 

내장되어 있는 함수들을 잘 이용하는 것이 중요하다는 것을 알 수 있네요ㅎ

 

많은 분들의 피드백은 언제나 환영합니다!  많은 댓글 부탁드려요~~