[백준] 1927번 최소 힙 JAVA (자바) 풀이

문제 1927번(자료구조, 우선순위 큐)

 :  최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오

1. 배열에 자연수 x를 넣는다 (비어있는 배열에서 시작)
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거

 

 

 [입력]

 :  첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)

 :  다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x (x 는 2³¹보다 작은 자연수 또는 0)

    (x가 자연수라면 배열에 x라는 값을 추가, 0이라면 배열에서 가장 작은 값을 출력하고 제거)

 

 [출력]

 :  입력에서 0이 주어진 횟수만큼 답을 출력 (만약 배열이 비어 있는 경우 0을 출력) 

 

 

 [설명]

 힙은 우선순위 큐와 원리가 비슷해 우선순위 큐로 구현할 수 있다

 

 우선순위 큐의 정렬 기준

 

 1. 기본은 오름차순

• PriorityQueue<Integer> pq = new PriorityQueue<>();
• 데이터들이 1-2-3-4-5 이런 식으로 오름차순으로 저장된다
   

 2. 반대로하면 내림차순

• Comparator.reverseOrder() 사용
• PriorityQueue<Integer> pq = new PriorityQueue<>( Comparator.reverseOrder());
• 데이터들이 5-4-3-2-1 이런 식으로 내림차순으로 저장된다 
  
  

 3. 커스텀 형식

• 람다 표현식 주로 사용
• (EX)   arr =  [ 5, 40 ], [ 4, 20 ], [ 1, 30 ] 라면
  • 2차원 배열인 [ A, B ] 에서 A는 0번째 B는 1번째라고 표현가능
  • (o1, o2) -> o1[0]-o2[0]   :  0번째 숫자 기준 오름차순   ▶ [ 1, 30 ] - [ 4, 20 ] - [ 5, 40 ]
  • (o1, o2) -> o1[1]-o2[1]   :  1번째 숫자 기준 오름차순   ▶ [ 4, 20 ] - [ 1, 30 ] - [ 5, 40 ] 
  • (o1, o2) -> o2[1]-o1[1]   :  1번째 숫자 기준 내림차순   ▶ [ 5, 40 ] - [ 1, 30 ] - [ 4, 20 ]
  • (o1, o2) -> o2[0]-o1[0]   :  0번째 숫자 기준 내림차순   ▶ [ 5, 40 ] - [ 4, 20 ] - [ 1, 30 ]   

 

 [코드]

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));
        int N = Integer.parseInt(br.readLine());
        Queue<Integer> pq = new PriorityQueue<>();
        
        for(int i=0;i<N;i++){
            int input = Integer.parseInt(br.readLine());
            if(input>0){
                pq.add(input);
            }
            else{
                if(!pq.isEmpty()){
                    System.out.println(pq.poll());
                }
                else{
                    System.out.println(0);
                }
            }
        }
    }
}

 

 [해설]
     

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());  첫째줄 입력
    Queue<Integer> pq = new PriorityQueue<>();  우선순위 큐 선언
        
 :  for(int i=0;i<N;i++){
            int input = Integer.parseInt(br.readLine());  N번의 입력들
            if(input>0){  자연수라면 큐에 추가하기
                pq.add(input);
            }
            else{  0이라면 큐에서 제거하고 출력하기
                if(!pq.isEmpty()){  빼낼 숫자가 존재한다면 큐에서 빼서 출력
                    System.out.println(pq.poll());
                }
                else{  빼낼 숫자가 존재하지 않는다면 0 출력
                    System.out.println(0);
                }
            }
    }
       

 

이제 풀어보러 갈께요 :)

 

 

 

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

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *