최소 힙(1927)

최소 힙(1927)

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));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    int n = Integer.parseInt(br.readLine());
    
    Queue<Integer> pq = new PriorityQueue<>();
    
    for(int i = 0; i < n; i++){
      int num = Integer.parseInt(br.readLine());
      
      if(num == 0){
        if(pq.peek() == null) sb.append(0).append("\n");
        else sb.append(pq.poll()).append("\n");
      } else{
        pq.add(num);
      }
    }
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
}

풀이과정

1. 처음에는 배열을 선언하고, 입력 받은 숫자에 따라 정렬과, 출력, 삭제 알고리즘을 구현하였다.
2. 메모리 초과가 발생하였다.
3. 그렇다면 불필요하게 배열을 크게 만들지 않고 할 수 있는 방법이 뭐가 있을까 고민하였다.
4. 배열은 크기를 선언하면 수정할 수 없기 때문에, 리스트로 해볼까 고민하다가, Deque를 이용하여 숫자를 비교하고 정렬시킬 수 있는 방법이 없을까 궁금해졌다.
5. 검색을 해보니 Queue에 PriorityQueue라는 것을 알게되었다.
6. PriorityQueue는 기본적인 정렬을 하게 되면 오름차순으로 구현되는데, 반대의 경우는 new PriorityQueue<>(Collections.reverseOrder()) 로 구현해야 했다.
7. 또는 특정 조건에 맞춰 만들 수도 있는데, 객체에 implements Comparable<객체>를 하여 compareTo 메소드를 오버라이드하여 우선순위를 구현할 수 있었다.

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));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    int n = Integer.parseInt(br.readLine());
    
    Queue<NumX> pq = new PriorityQueue<>();
    
    for(int i = 0; i < n; i++){
      int num = Integer.parseInt(br.readLine());
      NumX target = new NumX(num);
      
      if(num == 0){
        if(pq.peek() == null) sb.append(0).append("\n");
        else sb.append(pq.poll().getX()).append("\n");
      } else{
        pq.add(target);
      }
    }
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
  
  public static class NumX implements Comparable<NumX> {
    int x;
    
    public NumX(int x){
      this.x = x;
    }
    
    public int getX(){
      return x;
    }
    
    @Override
    public int compareTo(NumX target){
      if(this.x < target.getX()) return -1; // 낮은 애를 앞으로
      else if(this.x > target.getX()) return 1; // 크다면 뒤로
      else return 0; // 동등
    }    
  }
}

- 성공
- 메모리 : 26316 KB
- 시간 : 344 ms

보안점

1. PriorityQueue의 구현 원리를 더 공부해봐야겠다.