문제
널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
- 배열에 자연수 x를 넣는다.
- 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
해결 과정
최대 힙 문제에서 힙의 정렬 순서를 값이 가장 작을 때로 변경한 것과 동일하다.
최대 힙 문제와 동일하게 Priority Queue를 사용하되, reverseOrder 구문만 제거해 정순으로 정렬되게 하였다. 그 외에는 최대 힙 문제와 동일한 알고리즘을 구현하였다.
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); PriorityQueue<Integer> minHeap = new PriorityQueue<>(); StringBuilder sb = new StringBuilder(); int N = Integer.parseInt(br.readLine()); for(int i = 0; i < N;i++){ int x = Integer.parseInt(br.readLine()); //0 아닐때 if(x!=0){ minHeap.offer(x); } //0일때 else if(x==0){ if(!minHeap.isEmpty()){ int value = minHeap.poll(); sb.append(value).append("\n"); } else{ sb.append(0).append("\n"); } } } System.out.println(sb); } } |
이 또한 큰 문제 없이 정답임을 확인하였다.
'스파르타 알고리즘 트랙 문제(백준) > 6일차' 카테고리의 다른 글
스파르타 알고리즘 트랙 문제 6일차 - 3 #11047 동전 0 (0) | 2023.08.01 |
---|---|
스파르타 알고리즘 트랙 문제 6일차 - 2 #1037 약수 (0) | 2023.08.01 |