[백준] 11286 절댓값 힙 - Java / Python

 

 

 

https://13months.tistory.com/151

[백준] 11279 최대 힙 - Java / Python

전반적인 구성은 최대 힙 문제와 같지만, 절댓값이 같을 때에 대해서 처리 해 줘야 한다.

 

Java

우선순위 큐를 구현할 때 인자에 람다식으로 익명 함수를 넣어줬다. 

 

절댓값이 같은 경우 그 중에서 값이 더 작은 음수를 기준으로 우선순위 큐에 대해 오름차순 정렬을 진행하고, 아닌 경우에는 절댓값을 기준으로 오름차순 정렬을 진행한다.

 

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));
		StringBuilder sb = new StringBuilder();

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

		PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2) -> {
			int abs1 = Math.abs(o1);
			int abs2 = Math.abs(o2);
			if(abs1 == abs2){
				if(o1 > o2){
					return 1;
				}else{
					return -1;
				}
			}else{
				if((abs1-abs2)<0){
					return -1;
				}else{
					return 1;
				}
			}
		});

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

			if(command == 0){
				if(q.isEmpty()){
					sb.append(0).append('\n');
				}else{
					sb.append(q.poll()).append('\n');
				}
			}else{
				q.offer(command);
			}
		}

		System.out.println(sb);




	}
}

 

Python

 

파이썬으로 최대 힙을 구현할 때 튜플을 리스트에 넣어 앞의 숫자만 비교한 적이 있다.

절댓값 힙도 같은 방법으로 구현할 수 있다. 

 

튜플의 첫 번째 수를 기준으로 정렬하니, 앞쪽 숫자는 절댓값을 씌운 값으로 두고 뒷 숫자는 원래 값을 넣어주면 절댓값 정렬을 구현할 수 있다.

 

import heapq
import sys

N = int(input())
heap = []

for i in range(N):
    command = int(sys.stdin.readline())
    if command == 0:
        if heap:
            print(heapq.heappop(heap)[1])
        else:
            print(0)
    else:
        heapq.heappush(heap, (abs(command), command))