코딩 테스트/자료구조
[백준] 11286 절댓값 힙(실버1) - 힙(Heap), 우선순위 큐(PriorityQueue)
토자맨
2024. 6. 27. 19:08
문제
- 입력 값이 0이 아니라면 배열에 삽입
- 입력 값이 0이라면 절댓값이 가장 작은 값 출력하고 제거
- 만약 절댓값이 0이 아닌 값이 여러 개라면 그중 가장 작은 값을 출력하고 제거
예제
코드
시도1 - O
- 절댓값을 저장할 최소 힙(우선순위 큐)를 선언한다.
- [절댓값, 최소힙] 형태의 해시맵을 선언한다.
- N 크기만큼 순회하며 입력을 받는다.
- 0이 아닌 값을 입력받으면
- 힙에 입력 값이 존재하는지 확인
- 존재한다면
- 해시맵의 우선순위 큐 value에 입력 값 저장
- 존재하지 않는다면
- 힙에 절댓값 저장
- 해시맵의 Key로 절댓값 / value로 입력 값 힙 저장
- 존재한다면
- 힙에 입력 값이 존재하는지 확인
- 0을 입력받으면
- 절댓값 힙이 비어있는지 확인
- 비어있지 않다면
- 최소 절댓값 poll
- key가 최소 절댓값인 해시맵의 value를 poll하여 반환
- 비어있다면
- 0 반환
- 비어있지 않다면
- 절댓값 힙이 비어있는지 확인
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.HashMap;
public class _11286{ // Main으로 바꿔서 제출해야 함
public static void main(String [] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PriorityQueue<Integer> absolute_pq = new PriorityQueue<>();
HashMap<Integer, PriorityQueue<Integer>> hm = new HashMap<>();
int N = Integer.parseInt(br.readLine());
// 1. ----------------------------------------------------
for (int i = 0; i < N; i++) {
int num = Integer.parseInt(br.readLine());
// 2. ----------------------------------------------------
if (num != 0) {
absolute_pq.add(Math.abs(num));
if (!hm.containsKey(Math.abs(num))) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(num);
hm.put(Math.abs(num), pq);
// hm.put(Math.abs(num), new PriorityQueue(num));
}
else
hm.get(Math.abs(num)).offer(num);
}
// 3. ----------------------------------------------------
else { // 0
if (!absolute_pq.isEmpty()) {
int min = absolute_pq.poll();
System.out.println(hm.get(min).poll());
}
else
System.out.println(0);
}
}
}
}시도2 - O
우선순위 큐를 정의할 때 Comparator 인터페이스를 이용하여 우선순위를 설정할 수 있었다 .... ??
저번에 비슷한 문제가 있었던 것 같은데 기억 좀 하자 ^^
- 최소 힙을 선언한다.
- 입력 값의 절댓값과 힙에 있는 요소들의 절댓값을 비교
- 입력 값의 절댓값 > 힙에 있는 요소들의 절댓값 -> 힙에 있는 요소들의 절댓값이 우선
- 입력 값의 절댓값 < 힙에 있는 요소들의 절댓값 -> 입력 값의 절댓값이 우선
- 입력 값의 절댓값 == 힙에 있는 요소들의 절댓값 -> 원래 값이 작은 값이 우선
- 입력 값의 절댓값과 힙에 있는 요소들의 절댓값을 비교
- 입력 값이 0이면
- 0 반환
- 입력 값이 0이 아니면
- 최소 힙에 입력 값 삽입
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class Backjoon11286 {
private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(br.readLine());
PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
int abs1 = Math.abs(o1);
int abs2 = Math.abs(o2);
if(abs1 == abs2) return o1 > o2 ? 1 : -1;
return abs1 - abs2;
});
// 1. ----------------------------------------------------
for(int i = 0 ; i < n; i++){
int val = Integer.parseInt(br.readLine());
// 2. ----------------------------------------------------
if(val == 0){
if(queue.isEmpty()) System.out.println("0");
else System.out.println(queue.poll());
// 3. ----------------------------------------------------
}else{
queue.add(val);
}
}
}
}결론
우선순위 큐를 선언할 때 Comparator 인터페이스를 이용하여 우선순위를 설정할 수 있다.
return값에 따라 우선순위를 설정한다.
- return 값은 3가지로 나뉜다.
- 음수: 첫 번째 요소가 두 번째 요소보다 우선순위가 높음
- 0: 두 요소의 우선순위가 같음
- 양수: 첫 번째 요소가 두 번째 요소보다 우선순위가 낮음
아래 예시를 보자
- 입력 값(o1)의 절댓값과 우선순위 큐의 요소들(o2)의 절댓값이 같을 때
- 입력 값 > 요소 값: 양수(1) 반환 -> 입력 값의 우선순위가 요소 값의 우선순위보다 낮음
- 입력 값 < 요소 값: 음수(-1) 반환 -> 입력 값의 우선순위가 요소 값의 우선순위보다 높음
- 입력 값(o1)의 절댓값과 우선순위 큐의 요소들(o2)의 절댓값이 다를 때
- 입력 값의 절댓값 > 요소 값의 절댓값: 양수 반환 -> 입력 값의 우선순위가 요소 값의 우선순위보다 낮음
- 입력 값의 절댓값 < 요소 값의 절댓값: 음수 반환 -> 입력 값의 우선순위가 요소 값의 우선순위보다 높음
PriorityQueue<Integer> queue = new PriorityQueue<>(**이부분**)
PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
int abs1 = Math.abs(o1);
int abs2 = Math.abs(o2);
if(abs1 == abs2) return o1 > o2 ? 1 : -1;
return abs1 - abs2;
});꼭 기억하자 !!!