[알고리즘_코딩 테스트_JAVA] 절댓값 힙 구현하기 (JAVA, PYTHON)

본문은 알고리즘 코딩테스트 자바편을 정리한 내용입니다 :)

 

✔ 문제 014 절댓값 힙 구현하기

문제 바로가기 💨 

 

⬜ 핵심 아이디어

• x = 0 일때
  • 큐가 비어있을때는 0을 출력
  • 비어 있지 않을때는 절댓값이 최소인 값을 출력. 절댓값이 같다면 음수를 우선하여 출력
• x = 1 일때
  • add로 큐에 새로운 값을 추가하고 우선순위 큐 정렬 기준으로 자동 정렬

TIP : 람다함수에서 정렬 헷갈린다면, 양수면 첫번째(o1)가 뒤로.음수면 두번째(o2)가 뒤로 간다고 생각하면쉽다.

PriorityQueue<Integer> MyQueue = new PriorityQueue<>((o1, o2)->{
    int first_abs = Math.abs(o1);
    int second_abs = Math.abs(o2);
    if(first_abs == second_abs) {return o1 > o2 ? 1 : -1;} // 절댓값이 같으면 음수 우선 정렬
    else {return first_abs - second_abs;} // 절댓값 기준 정렬
});

슈도코드 작성하기

N(질의 요청 개수)
우선순위 큐 선언
- 절댓값 기준으로 정렬되도록 설정
- 단, 절댓값 같으면 음수 우선 정렬하기
for(N만큼 반복)
{
	요청 0일때: 큐가 비어 있으면 0, 비어 있지 않으면 큐의 front 값 출력하기(poll())
    요청 1일때: 새로운 데이터를 우선순위 큐에 더하기 (add())
}

JAVA

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.PriorityQueue;

class Main {
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    int N = Integer.parseInt(br.readLine()); // 연산개수
	    PriorityQueue<Integer> MyQueue = new PriorityQueue<>((o1, o2)->{
	        int first_abs = Math.abs(o1);
	        int second_abs = Math.abs(o2);
	        if(first_abs == second_abs) {return o1 > o2 ? 1 : -1;} // 절댓값이 같으면 음수 우선 정렬
	        else {return first_abs - second_abs;} // 절댓값 기준 정렬
	    });
	    for(int i = 0; i < N; i++){
	        int request = Integer.parseInt(br.readLine());
	        if(request == 0) { // 출력
	            if(MyQueue.isEmpty()) {System.out.println("0");}
	            else {System.out.println(MyQueue.poll());}
	        } else{ // 0 아니면 add
	            MyQueue.add(request);
	        }
	    }
	}
}

PYTHON

import sys, heapq

abs_heap = []
N = int(sys.stdin.readline())

for i in range(N):
    num = int(sys.stdin.readline())
    if num: # 출력 X,삽입
        heapq.heappush(abs_heap, (abs(num), num))
    else: # 출력
        if abs_heap:
            print(heapq.heappop(abs_heap)[1])
        else:
            print(0)