[백준] 11286 - 절댓값 힙 JAVA

Solved.ac Class 완전정복 프로젝트

Class : 3 ~ 3 ++

 

---

링크

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

11286번: 절댓값 힙

문제

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

배열에 정수 x (x ≠ 0)를 넣는다.
배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러 개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.

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

접근방법

 1927

최소힙 문제와 같이 우선순위 큐를 이용한다. 단, 우선순위 큐는 기본적으로 낮은 순서로 높은 우선순위를 부여하지만, 이번 문제에서는 특수한 조건이 있다는 것을 확인하고 풀이로 들어가자.

풀이

  우선순위큐에 순위 선정방식을 조절하면 문제는 끝난다. 람다식을 이용하여, 절댓값 비교와 수가 같을 때 낮을 수를 출력할 수 있도록 순위를 정의하고 문제에 요구에 따라 풀면 끝이다. 

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        Main test =new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
            int abs_a = Math.abs(o1);
            int abs_b = Math.abs(o2);
            if(abs_a ==abs_b){
               return o1.compareTo(o2);
           }else{
               return (abs_a - abs_b) < 0 ? -1 : 1;
           }
        });

        StringBuilder sb = new StringBuilder();


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

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

        }

        System.out.println(sb);

    }


}

결과

 

 

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.