[ Baekjoon - 10/21 ] - 1927번: 최소 힙

• 문제 링크 : https://www.acmicpc.net/problem/1927

1927번: 최소 힙

 

소요시간 : 자바 파이썬 둘다 코딩하는 시간 포함 15분정도. 행복한 문제~

이번 문제는 솔브닥 클래스를 올리고싶어서 풀게된 문제로, 최소힙을 구현할 수 있는지에 관한 문제이다!

---

 

우선 힙을 어떻게 구현해야하는지 살펴보자!

 

1. 자바의 경우
   • PriorityQueue를 이용해 최소힙과 최대힙 둘다 구현 가능하다
     만약 사용자 정의 Class를 큐로 쓰고싶다면,  Comparable이나 Comparator를 이용해 우선순위를 설정해야한다.

   • import java.util.*;
     
     // 최소힙
     PriorityQueue<Integer> minHeap = new PriorityQueue<>();
     
     // 최대힙
     PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

2. 파이썬의 경우
   • 최소힙, 최대힙 둘다 heapq 라이브러리를 이용해 구현하되, 최소힙이 default이므로 최대힙을 구현하기 위해서는 마이너스를 붙인다.

   • import heapq
     
     # 최소힙
     minHeap = []
     heapq.heappush(heap, n)
     
     # 최대힙
     minHeap = []
     heapq.heappush(heap, (-n, n))

이를 구현할 수 있으면 위 문제는 매우 간단하다.

---

• 풀이 코드
  1. Java 11

     • import java.util.*;
       import java.io.*;
       
       public class Main{
           static int N,x;
       
           public static void main(String[] args) throws IOException {
               //System.setIn(new FileInputStream("src/input.txt"));
               BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
               N = Integer.parseInt(br.readLine());
       
               PriorityQueue<Integer> pq = new PriorityQueue<>();
               while(N-->0){
                   x = Integer.parseInt(br.readLine());
                   if(x==0){
                       if(pq.isEmpty()){
                           System.out.println(0);
                       }else{
                           System.out.println(pq.remove());
                       }
                   }else{
                       pq.add(x);
                   }
               }
           }
       }

  2. Python 3

     • import sys
       import heapq
       input = sys.stdin.readline
       
       N = int(input())
       pq = []
       for _ in range(N):
           x = int(input())
           if x==0:
               if len(pq)==0:
                   print(0)
               else:
                   print(heapq.heappop(pq))
           else:
               heapq.heappush(pq, x)

 

• 결과