https://www.acmicpc.net/problem/1927
문제
널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
- 배열에 자연수 x를 넣는다.
- 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
입력
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다.
출력
입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.
나의 문제 풀이
1) 최대 힙을 반대로 생각하면 최소 힙을 구할 수 있다.
2) PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(); 이렇게 사용하면 Defalut 값으로 내림차순이 되어 최소 값을 우선순위로 출력 할 수 있다.
import java.io.*;
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 n = Integer.parseInt(br.readLine());
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
for(int i = 0; i < n; i++){
int a = Integer.parseInt(br.readLine());
if(a == 0) {
if (priorityQueue.size() == 0) {
sb.append(0).append('\n');
} else {
sb.append(priorityQueue.poll()).append('\n');
}
}
else{
priorityQueue.add(a);
}
}
System.out.println(sb);
}
}
'코드문제풀이 > JAVA' 카테고리의 다른 글
[자바] 11050번 이항 계수 1 (0) | 2023.07.29 |
---|---|
[자바] 1541번 잃어버린 괄호 (0) | 2023.07.29 |
[자바] 1037번 약수 (0) | 2023.07.29 |
[자바] 11047번 동전 0 (0) | 2023.07.29 |
[자바] 11866번 요세푸스 문제 0 (0) | 2023.07.28 |