7. 최소 힙

내가 푼 코드

package com.company;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
      
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> minHeep = new ArrayList();
        int count = Integer.parseInt(br.readLine());

        for(int i = 0; i < count; ++i) {
            int minNum = Integer.parseInt(br.readLine());
            if (minNum > 0) {
                minHeep.add(minNum);
            }

            if (minNum == 0) {
                if (minHeep.isEmpty()) {
                    System.out.println(0);
                } else {
                    int min = (Integer)Collections.min(minHeep);
                    System.out.println(min);

                    for(int j = 0; j < minHeep.size(); ++j) {
                        if ((Integer)minHeep.get(j) == min) {
                            minHeep.remove(j);
                        }
                    }
                }
            }
        }

    }
}

IDE에서는 입력/출력이 백준 문제대로 정상 작동 하는데 제출하니 시간 초과가 떳다.

---

package com.company;

import java.io.*;

import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;


public class Main {

    // < 최소 힙 > 문제
    // 1. 배열에 자연수를 넣는다
    // 2. 배열에서 가장 작은 값 출력 후, 그 값은 배열에서 삭제
    // 비어있는 배열에서 시작하기

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> minQueue = new PriorityQueue<Integer>();

        int count = Integer.parseInt(br.readLine());

        for (int i = 0; i < count; i++){

            int input = Integer.parseInt(br.readLine());

            if(input > 0) minQueue.add(input);

            if(input == 0){
                if(!minQueue.isEmpty()){
                    System.out.println(minQueue.poll());
                } else {
                    System.out.println(0);
                }
            }
        }
    }
}

 

 

그래서 검색했더니 나온 방법은

priorityQueue 

PriorityQueue는 Java에서 제공하는 우선순위 큐(priority queue)를 구현한 클래스입니다.

우선순위 큐는 요소들이 우선순위에 따라 정렬되어 있는 자료구조입니다.

이 자료구조에서는 항상 가장 높은 우선순위를 갖는 요소가 먼저 제거됩니다.

 

PriorityQueue는 일반적인 큐(queue)와 달리 요소들을 FIFO(First-In-First-Out, 선입선출) 순서가 아닌

우선순위에 따라 제거합니다. 따라서 PriorityQueue에 삽입된 요소들은 일반적인 큐와는 다르게 정렬되어 있습니다.

PriorityQueue는 힙(heap)을 사용하여 내부적으로 요소들을 관리합니다.

이는 요소들을 우선순위에 따라 효율적으로 정렬하고 삽입/삭제 연산을 수행할 수 있게 합니다.

 

PriorityQueue의 특징은 다음과 같습니다:

1. 요소들이 우선순위에 따라 정렬됩니다.
2. 요소들의 정렬은 요소들 간의 비교에 의해 이루어집니다. 이를 위해 Comparable 또는 Comparator 인터페이스를 구현하여 우선순위를 결정할 수 있습니다.
3. 가장 높은 우선순위를 가진 요소가 제일 먼저 제거됩니다.
4. 힙(heap) 자료구조를 사용하여 내부적으로 요소들을 관리합니다.

PriorityQueue는 우선순위 큐의 특성을 활용하여 다양한 알고리즘 및 문제 해결에 활용됩니다.

예를 들어 다익스트라 알고리즘 등의 그래프 알고리즘에서 최단 경로를 찾는 데 활용될 수 있습니다.

 

 

---

새로 배운 것

 

1. BufferedReader가 Scanner 보다 빠르다, 그치만 BufferedReader 쓸 때는 예외처리를 해줘야한다.

- throws NumberFormatException, IOException

 

2. isEmpty () 메서드는 배열이 빈 값인지 아닌지 검사해준다

 

3. Collections.min() 은 배열의 가장 작은 값을 알려준다