Do it! 알고리즘 코딩테스트(14번)

14번 문제 절댓값 힙 구현하기

---

내가 떠올린 풀이 해설

배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 제거하는 것에서 PriorityQueue를 떠올렸습니다.

PriorityQueue는 add를 하면 오름차순으로 정렬이 되는 Queue입니다. PriorityQueue에 넣어서 값을 비교해서 절댓값이 작은 값을 출력하고 절댓값이 같을 때는 수의 작은 값을 출력하는 문제다.

---

정확한 풀이

import java.io.*;
import java.util.*;

public class Baek11286 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
		int n = Integer.parseInt(br.readLine());
		
		PriorityQueue<Integer> que = new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				int a1 = Math.abs(o1);
				int a2 = Math.abs(o2);
				if(a1 == a2) {
					return Integer.compare(o1, o2);
				}
				else {
					return Integer.compare(a1, a2);
				}
			}
		});
		
		for(int i = 0 ; i < n ; i++) {
			int num = Integer.parseInt(br.readLine());
			if(num == 0) {
				if(que.size() == 0) {
					System.out.println(0);
				}
				else {
					System.out.println(que.poll());
				}
			}
			else {
				que.add(num);
			}
		}
	}
}

---

문제점

PriorityQueue에 add를 하면 PriorityQueue의 성질 때문에 add 한 순으로오름차순으로 정렬이 되는데 거기서 절댓값을 어떻게 비교 어떻게 해야될지를 떠올리지 못했다. compare를 사용해서 절댓값 문제를 해결할 수 있었다. 정렬 문제에서 compare를 이용하는 문제가 많으므로 compare를 공부를 하자.

 

오늘의 회고

오늘은 그동안 푼 문제 복습과 1문제 밖에 풀지 못했습니다. 알고리즘을 처음 공부하는데 이해하고 문제를 해결하는 방식을 떠올리는 것이 많이 어려운것 같습니다. 포기 하지 않고 하반기까지 실력을 향상 시키는 것을 목표로 꾸준히 달려보겠습니다.