[BOJ - JAVA] 1927, 11279 - 최소 힙, 최대 힙(우선순위 큐)

최소 힙

# 주소

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

1927번: 최소 힙

# 문제

# 문제 해설 및 코드 리뷰

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

public class Main {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(x->x));
        for(int i = 0; i < n; i++){
            int x = Integer.parseInt(br.readLine());
            if(x == 0){
                if(queue.isEmpty())
                    System.out.println("0");
                else
                    System.out.println(queue.poll());
            }else
                queue.offer(x);
        }
    }
}

원래 Scanner로 풀었는데 시간초과가 나서 Buffer로 풀었습니다.

예전 블로그 포스팅에서도 한 번 등장한 개념인 Comparator 인터페이스를 활용한 문제입니다.

우선순위 큐 문제도 코딩테스트에서 빈번하게 나오기 때문에 대비가 필요하다고 생각해서 풀었습니다.

기본적으로 우선순위 큐는 'PriorityQueue'라고 사용하는데, 큐의 성격을 띄되 우선순위가 정해져 있는 큐라고 생각할 수 있겠습니다.

Queue에서 원소를 빼오거나 출력하는 등의 동작 방식은 기존의 Queue와 똑같지만 딱 한가지 다른점은 Queue에서는 '선입선출' 구조(FIFO)를 따르기 때문에 먼저 들어간 원소가 먼저 출력되는 반면, PriorityQueue는 예를들어 최소값이라던지, 최대값을 우선적으로 출력할 수 있습니다.

위의 문제에서 상기된 풀이는 최소 힙을 나타내는 문제로서 값이 주입될 때 만들어진 Queue에서 최소값을 출력하게끔 되어 있으므로 이럴 땐 Comparator인터페이스를 사용합니다.

람다식을 이용해서 주로 푸는 것이 특징입니다.

        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(x->x));

그래서 PriorityQueue를 선언할 때 Comparator.comparintInt(x -> x)라고 한다면 이는 각 원소를 비교하여 오름차순으로 정렬하겠다는 뜻이 됩니다.

그렇기 때문에 원소가 한 번 삽입되면 한 번 정렬할 때 N의 시간이 걸리므로 N번 데이터가 삽입되면 N^2만큼 시간복잡도가 걸린다고도 할 수 있습니다.

이렇게만 선언하기만 해도 아래의 부분에선 기존의 Queue문제와 전혀 다를바가 없습니다.

   for(int i = 0; i < n; i++){
            int x = Integer.parseInt(br.readLine());
            if(x == 0){
                if(queue.isEmpty())
                    System.out.println("0");
                else
                    System.out.println(queue.poll());
            }else
                queue.offer(x);
        }
    }
}

for문을 이용하여 x를 입력받고 x가 0이고 queue가 비어있으면 0출력, 아니면 queue의 최소값 출력을 하고 x가 0이 아니라면 그냥 최소값을 출력하면 정답이 됩니다.

그럼 이제 최대 힙은 어떻게 푸는지 한 번 살펴봅시다.

 

최대 힙

# 주소

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

11279번: 최대 힙

# 문제 

# 문제 해설 및 코드 리뷰

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

public class Main {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2-o1);
        for(int i = 0; i < n; i++){
            int x = Integer.parseInt(br.readLine());
            if(x == 0){
                if(queue.isEmpty())
                    System.out.println("0");
                else
                    System.out.println(queue.poll());
            }else
                queue.offer(x);
        }
    }
}

 

위의 최소 힙 문제와 상당히 유사한 것을 알 수 있습니다.

다만 한 가지 다른 부분은, Compartor인터페이스를 이용하지 않았다는 점입니다.

기본적으로 모든 배열은 정렬을 할 때 오름차순을 기본적으로 베이스라고 생각하고 내림차순을 reverseOrder로 여깁니다.

여기에서는 comparator인터페이스를 사용하지 않은것처럼 보이지만 실은 그렇지 않습니다.

람다를 통해 Comparator를 인스턴스로 만든 것이기 때문입니다. (위의 문제처럼 똑같이 Comparator를 사용했습니다.)

위의 최소 힙 문제도 저것보다 더 쉽게 풀 수 있습니다.

        PriorityQueue<Integer> queue = new PriorityQueue<>((x1,x2) -> x1 - x2);

이런식으로 만들어서 해도 되는 것이지요.

하지만 이것보다는 대부분 오름차순으로 표기하고 싶을 땐 

        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(x -> x));

이렇게 쓰고

내림차순으로 표기하고 싶을 땐

        PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2) -> o2 - o1);

이렇게 많이들 쓰더라고요..

제가 경험이 부족해서 왜 하나로 통일해서 쓰지 않는지는 잘 모르겠습니다만 달리 아시는 분은 알려주심 감사하겠습니다.

https://beomseok95.tistory.com/281

Java - Comparable, Comparator

시간 나시면 이거 읽어보시는 것도 상당히 도움 됩니다.