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

[백준 11286번 / Java] 절댓값 힙P.S./백준2023. 7. 13. 23:36@mag1c

Table of Contents

728x90

문제 링크

Silver 1

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

11286번: 절댓값 힙

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

풀이

자료구조와 정렬만 잘 할줄 안다면 풀 수 있는 문제로 개인적으로 같은 난이도의 DP보다는 훨씬 쉽다고 생각

DP는 생각할 시간이 필요한데 이건 술술 풀렸으니까

힙 구조는 최대 / 최소값을 찾아내는 연산을 빠르게 하기 위한 완전 이진트리를 기반으로 한 자료구조로

자바에서는 우선순위 큐인 PriorityQueue를 사용해서 구현하며 기본값은 오름차순 정렬이다.

상황에 따라 내림차순, 혹은 이번 문제처럼 Comparator 인터페이스를 통해 정렬을 직접 구현하면 된다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (Math.abs(o1) == Math.abs(o2)) return o1 - o2;
                else return Math.abs(o1) - Math.abs(o2);
            }
        });
        for (int i = 0; i < N; i ++) {
            int x = Integer.parseInt(br.readLine());

            if(x == 0) {
                int out = queue.isEmpty() ? 0 : queue.poll();
                System.out.println(out);
            }
            else queue.offer(x);
        }

    }
}

728x90