문제 설명
이 문제는 주어진 연산에 따라 배열에 자연수를 넣거나, 배열에서 가장 작은 값을 가져오는 작업을 최소 힙을 통해 효율적으로 처리하는 문제이다.
기본적으로 배열에 값을 넣거나 가장 작은 값을 제거하고 출력하는 작업을 반복해야하는데 여기에서 중요한 점은 0이 주어졌을 때 배열에서 가장 작은 값을 출력해야 한다는 것 !
초기 접근 방법과 문제점
맨 처음에는 일단 동작 구현에 초첨을 맞춰서 빨리 풀 생각을 했다. 제한시간이 30분인점을 보고 막연히 간단하게 구현만 하면 되는구나 라고 생각했었다.
- 큐를 사용해 값을 저장하고,
0이 입력될 때마다 큐에서 가장 작은 값을 찾아 출력한다. - 큐에서 가장 작은 값을 찾기 위해 매번
Collections.min()을 호출한다.
-> 이것이 시간 초과의 가장 큰 원인이 됐던 것으로 보인다.
처음 코드
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));
int N = Integer.parseInt(br.readLine());
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < N; i++) {
int num = Integer.parseInt(br.readLine());
if (num != 0) {
queue.add(num);
} else {
if (queue.size() == 0) {
bw.write("0\n");
} else {
int min = Collections.min(queue); // 가장 작은 값 찾기
bw.write(min + "\n");
queue.remove(min); // 가장 작은 값 제거
}
}
}
bw.flush();
bw.close();
br.close();
}
}시간 초과 발생 !!!
Collections.min()을 호출하여 가장 작은 값을 찾는 작업 수행했지만... Collections.min()은 리스트 전체를 탐색하기 때문에 시간 복잡도가 O(N)이라는 사실을 간과했다.
매번 가장 작은 값을 찾고 제거하는 작업을 반복해야 하기 때문에 전체 복잡도는 O(N^2)에 가까워질 수 밖에 없었다.
입력 범위도 신경써야 한다는 사실을 또 한 번 깨달았다... :<
해결 방안 : PriorityQueue를 사용한 최소 힙
사실 최소 힙이라는 단어만 보고도 PriorityQueue를 생각해냈어야 하는 것인데 자료구조 진도를 천천히 나가고 있으니 생각이 나지 않더라. (공부속도를 높여야겠음!)
가장 작은 값을 O(log N) 시간 복잡도로 삽입 및 제거할 수 있는 최소 힙을 PriorityQueue를 통해 구현할 수 있다.
1. add() : 새로운 값을 힙에 추가. O(log N)
2. poll() : 가장 작은 값을 제거하고 반환.
=> 최소 힙의 특성상 가장 작은 값이 항상 루트에 위치하기 때문에 이 작업도 O(log N) !!!
최적화된 코드
import java.io.*;
import java.util.PriorityQueue;
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));
int N = Integer.parseInt(br.readLine());
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int i = 0; i < N; i++) {
int x = Integer.parseInt(br.readLine());
if (x > 0) {
minHeap.add(x); // 자연수는 최소 힙에 추가
} else {
if (minHeap.isEmpty()) {
bw.write("0\n");
} else {
bw.write(minHeap.poll() + "\n"); // 최소값 출력 후 제거
}
}
}
bw.flush();
bw.close();
br.close();
}
}결론
- PriorityQueue는 힙을 사용하여 효율적인 최소값 접근을 제공한다.
- 큐의 전체 탐색이 필요할 때는 비효율적이지만 최소값 또는 최대값 접근이 빈번한 경우에는 최소 힙 또는 최대 힙을 사용하는 것이 효율적이다.
