내가 푼 코드
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의 특징은 다음과 같습니다:
- 요소들이 우선순위에 따라 정렬됩니다.
- 요소들의 정렬은 요소들 간의 비교에 의해 이루어집니다. 이를 위해 Comparable 또는 Comparator 인터페이스를 구현하여 우선순위를 결정할 수 있습니다.
- 가장 높은 우선순위를 가진 요소가 제일 먼저 제거됩니다.
- 힙(heap) 자료구조를 사용하여 내부적으로 요소들을 관리합니다.
PriorityQueue는 우선순위 큐의 특성을 활용하여 다양한 알고리즘 및 문제 해결에 활용됩니다.
예를 들어 다익스트라 알고리즘 등의 그래프 알고리즘에서 최단 경로를 찾는 데 활용될 수 있습니다.
새로 배운 것
1. BufferedReader가 Scanner 보다 빠르다, 그치만 BufferedReader 쓸 때는 예외처리를 해줘야한다.
- throws NumberFormatException, IOException
2. isEmpty () 메서드는 배열이 빈 값인지 아닌지 검사해준다
3. Collections.min() 은 배열의 가장 작은 값을 알려준다
'코딩테스트' 카테고리의 다른 글
9. 숫자 카드 2 (0) | 2024.05.12 |
---|---|
8. 최대 힙 (1) | 2024.04.28 |
6. 코딩은 체육과목 입니다 | repeat() 문자열 반복 함수 (0) | 2023.02.26 |
5. 빠른 A+B (BufferedReader, BufferedWriter) (0) | 2023.02.12 |
4. 오븐 시계 | 입력받은 시간에서 20분 더한 시간 출력 (0) | 2023.01.23 |