[백준] 11286번 : 절댓값 힙

문제

 

 

접근 방식

우선순위큐 최소힙을 사용해서 풀 수 있는 문제로

직접 구현해서 풀 수도 있지만 자바에서 제공하는 우선순위 큐를 사용하여 풀었다.

 

두 가지 방식으로 풀어봤는데 첫 번째는 우선순위 큐의 생성자에

파라미터로 정렬 기준을 제공해 문제에서 요구하는 순서대로 정렬되게 하는 방법이고

 

두 번째 방법은 우선순위 큐에 모두 절댓값으로 변환해 양수인 값만 저장하면서

맵에 음수인 경우만 카운팅 하는 방법이다.

 

우선 첫 번째 방법부터 살펴보면

정렬기준을 절댓값이 같다면 더 작은 값이 먼저 나와야 하니

abs(x) == abs(y) 라면 x - y를 리턴해주고

두 수의 절댓값이 다르다면 절댓값이 더 작은 수가 앞에 오면 되니

abs(x) - abs(y)를 리턴해주면 된다.

 

두 번째 방법은 자바에서 우선순위 큐의 기본 원리가 최소힙이 적용된 상태니

입력받은 수를 모두 양수로 바꾸어서 큐에 저장한다.

 

이때 입력 받은 수가 음수라면 따로 만들어둔 맵에 해당 절댓값을 키로 가진

값을 1씩 증가시키고 입력으로 0이 들어올 때마다

음수가 카운팅 된 게 남아있으면 음수로 바꾸어 출력해 주고 카운트를 1씩 줄여주면 되고

카운팅이 남아있지 않다면 양수를 출력해 주면 된다.

 

풀이

첫 번째 풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

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

		PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->
			Math.abs(a) == Math.abs(b) ? (a - b) : (Math.abs(a) - Math.abs(b)));

		for (int i = 0; i < n; i++) {
			int x = Integer.parseInt(br.readLine());

			if (x != 0) {
				pq.offer(x);
			} else {
				sb.append(pq.isEmpty() ? 0 : pq.poll()).append("\n");
			}
		}

		System.out.println(sb);
	}
}

 

두 번째 풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

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

		PriorityQueue<Integer> pq = new PriorityQueue<>(n);
		Map<Integer, Integer> countMap = new HashMap<>();

		for (int i = 0; i < n; i++) {
			int x = Integer.parseInt(br.readLine());

			if (x != 0) {
				int abs = Math.abs(x);
				int count = countMap.getOrDefault(abs, 0);

				if (x < 0) count++;

				countMap.put(abs, count);

				pq.offer(abs);
			} else {
				if (pq.isEmpty()) sb.append(0).append("\n");
				else {
					int num = pq.poll();
					int count = countMap.get(num);

					if (count != 0) {
						sb.append(-num).append("\n");
						countMap.put(num, count - 1);
					} else {
						sb.append(num).append("\n");
					}
				}
			}
		}

		System.out.println(sb);
	}
}