코딩 테스트 [자료구조] - 절댓값 힙 구현하기

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조다.

1. 배열에 정수 x(x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력한 후, 그 값을 배열에서 제거한다. 절댓값이 갖아 작은 값이 여러 개일 경우에는 그중 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비여 있는 배열에서 시작한다. 절댓값 힙을 구현하시오.

---

입력

1번째 줄에 연산의 개수 N(1 ⪯ N ⪯ 100,000)이 주어진다. 다음 N개의 줄에는 연산과 관련된 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열 x라는 값을 추가하고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 입력되는 정수는 -231보다 크고, 231보다 작다.

출력

입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는데 절댓값이 가장 작은 값을 출력하라고 할 때는 0을 출력하면 된다.

예제 입력
18	// 연산의 개수
1
-1
0
0
0
1
1
-1
-1
2
-2
0
0
0
0
0
0
0

예제 출력
-1
1
0
-1
-1
1
1
-2
2
0

---

1단계 - 문제 분석하기

N의 최대 범위가 100,000이므로 O(nlogn) 시간 복잡도를 가진 알고리즘으로 풀 수 있다. 절댓값과 관련된 정렬이 필요하므로 우선순위 큐로 문제를 해결할 수 있다. 단 이 문제는 절댓값 정렬이 필요하므로 우선순위 큐의 정렬 기준을 직접 정의해야 한다.

2단계 - 손으로 풀어 보기

문제 푸는 순서

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

3단계 - sudo코드 작성하기

N(질의 요청 개수)
우선순위 큐 선언
- 절댓값 기준으로 정렬되도록 설정
- 단, 절댓값이 같으면 음수 우선 정렬하기

for(N만큼 반복) {
	요청이 0일 때 : 큐가 비어 있으면 0, 비어 있지 않으면 큐의 front값 출력(poll)
    요청이 0이 아닐 때 : 새로운 데이터를 우선순위 큐에 더하기(add)
}

4단계 - 코드 구현하기

우선순위 큐에서 정렬 기준을 설정하는 방법에 주목하자.

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

public class Q14 {
    public static void main(String[] args) throws IOException {

        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);

           // o1에 높은 우선순위를 주고싶다면 음수 return, o2에 높은 우선순위를 주고싶다면 양수 return
           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 {
                myQueue.add(request);
            }
        }
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편