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

 

1927번: 최소 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

코드설명

우선순위큐를 활용하여 최소힙을 구하는 문제입니다.

 

단순히, 우선순위큐를 사용할 줄 안다면 쉽게 해결할 수 있습니다.

 

코드

코드1입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class Main {
	
	public static int N, K;
	public static String[] arr;
	public static PriorityQueue<Node> pq = new PriorityQueue<Node>();
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
 
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		if( a == 0 && pq.size() == 0) {
    			System.out.println("0");
    			
    		} else if( a == 0 && pq.size() > 0) {
    			System.out.println(pq.poll().value);
    		} else if( a > 0) {
    			pq.offer(new Node(a));	
    		}
    	}
   
    }
    
}

 

코드 2입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = 0;
	public static PriorityQueue<Integer> pq = new PriorityQueue<>();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			if(x > 0) {
				pq.add(x);
			}
			if(x == 0) {
				if(pq.isEmpty()) System.out.println(0);
				else System.out.println(pq.poll());
			}
		}
		
	}
	
	
}

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 1406 에디터 - 연결리스트 + 링크드리스트 JAVA  (0) 2023.08.08
[백준] 11501 주식 - 탐욕법(Greedy, 그리디) + 우선순위큐(PriorityQueue)JAVA  (0) 2023.08.07
[백준] 19941 햄버거 분배 - 그리디(탐욕법, Greedy) JAVA  (0) 2023.08.07
[백준] 3109 빵집 - 그리디 + DFS JAVA  (0) 2023.08.01
[백준] 15591 MooTube (Silver) - 그래프 + DFS + BFS JAVA  (0) 2023.08.01

+ Recent posts

티스토리툴바