[백준] 11286번 - 절댓값 힙 [Java]

https://www.acmicpc.net/problem/11286

 

[백준] 11286번 - 절댓값 힙 [Java]

[백준] 11286번 - 절댓값 힙 [Java]

---

1.  아이디어

 

자바에서 힙을 구현하는 PriorityQueue을 이용하면 간단하게 구현할 수 있다.

---

2. 문제풀이

 

PriorityQueue의 정렬 기준을 문제 조건에 맞게 절댓값을 기준으로 하고 절댓값이 동일하면 작은 수가 앞에 오게 람다식으로 구현하는 방법과 최소힙, 최대힙 두 개를 활용해서 최소힙에는 양수, 최대힙에는 음수를 저장한 후 조건 분기로 처리하는 방법 2가지로 구현했다.

 

람다식은 두 수의 합이 0이면 절댓값이 동일한 음수와 양수 조합이 되므로 이때는 그냥 정렬을 하고 이게 아닌 경우에는 절댓값으로 정렬하도록 짰다.

 

최소힙, 최대힙은 우선순위 큐가 비었을 때에 대한 조건분기만 꼼꼼하게 해주는 방식으로 구현했다.

---

3. 코드

 

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

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

        PriorityQueue<Integer> pqPositive = new PriorityQueue<>();
        PriorityQueue<Integer> pqNegative = new PriorityQueue<>(Collections.reverseOrder());

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

            if (x > 0) pqPositive.add(x);
            else if (x < 0) pqNegative.add(x);
            else {
                if (pqPositive.isEmpty() && pqNegative.isEmpty()) sb.append(0).append("\n");
                else if (pqPositive.isEmpty()) sb.append(pqNegative.poll()).append("\n");
                else if (pqNegative.isEmpty()) sb.append(pqPositive.poll()).append("\n");
                else {
                    if (pqPositive.peek() + pqNegative.peek() >= 0) {
                        sb.append(pqNegative.poll()).append("\n");
                    } else {
                        sb.append(pqPositive.poll()).append("\n");
                    }
                }
            }
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

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

        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
            if(o1 + o2 != 0) return Integer.compare(Math.abs(o1), Math.abs(o2));
            return Integer.compare(o1, o2);
        });

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

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

        bw.write(sb.toString());
        bw.flush();
    }
}

---

4. 후기

 

- 람다식

- 최소힙, 최대힙