[JAVA] 백준 11279 최대 힙

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

11279번: 최대 힙

 

- 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램 

 

1. 배열에 자연수 x를 넣는다,

2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

 

- x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산

- x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우 

- 만약 배열에 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력 

 

 

문제 풀이 

 

우선순위 큐(Priority Queue)

 

[Java] PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리 (tistory.com)

[Java] PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리

 

- 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조 (FIFO)

- 우선순위 큐는 먼저 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조 

- 우선순위 큐는 힙을 이용하여 구현하는 것이 일반적 

- 데이터를 삽입할 떄 우선순위를 기준으로 최대힙 또는 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행 

 

-최대 값이 우선순위인 큐 = 최대힙, 최소 값이 우선순위인 큐 = 최소힙

 

1) 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조 

(큐에 들어가는 원소는 비교가 가능한 기준이 있어야 함)

 

2) 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있음

 

3) 내부구조가 힙으로 구성되어 있기에 시간 복잡도 O(NlogN)

 

4) 응급실과 같이 우선순위를 중요시해야 하는 상황에서 쓰임 

 

 

Priority Queue 사용법 

 

1) 선언

import java.util.PriorityQueue; 

//int형 PriorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<Integer> pq = new PriorityQueue<>();

//int형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

 

- 자바에서 우선순위 큐 라이브러리를 사용하고 싶다면 java.util.PriorityQueue를 import

- 기본은 우선순위가 낮은 숫자가 부여

- 높은 숫자가 우선순위가 되게 하고 싶다면 선언 시 Collections.reverseOrder() 메서드를 이용 

 

 

2) 값 추가

 

pq.add(1); 
pq.add(2);
pq.offer(3);

 

- 값을 추가하고 싶다면 add(value) 또는 offer(value)라는 메서드를 활용하면 됨 

- add(value) 메서드의 경우 만약 삽입에 성공하면 true를 반환하고, 큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생 

 

 

3) 값 삭제 

 

pq.poll(); //PriortiyQueue에 첫 번째 값을 반환 
pq.remove(); //PriorityQueue에 첫 번째 값 제거 
pq.clear(); //PriorityQueue에 초기화

 

- 우선순위 큐에서 값을 제거하고 싶다면 poll()이나 remove() 메서드를 사용하면 됨 

- 값을 제거할 시 우선순위가 가장 높은 값이 제거됨 

- poll() 함수는 우선순위 큐가 비어있으면 null을 반환 

- pop을 하면 가장 앞 쪽에 있는 원소의 값이 제거 

 

 

4) 우선순위가 가장 높은 값 출력 

 

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(2);     // priorityQueue에 값 2 추가
pq.offer(1);     // priorityQueue에 값 1 추가
pq.offer(3);     // priorityQueue에 값 3 추가
pq.peek();       // priorityQueue에 첫번째 값 참조 = 1

 

 

정답 

 

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

public class Main {
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        //우선순위가 높은 순 = 최대힙
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        int N = Integer.parseInt(br.readLine());
        
        StringTokenizer st;
        for(int i=0; i<N; i++)
        {
            st = new StringTokenizer(br.readLine());
            int value = Integer.parseInt(st.nextToken());
            
            //값 제거 
            if(value == 0)
            {
                if(pq.isEmpty())
                {
                    sb.append("0").append("\n");
                }
                else
                {
                    int ans = pq.poll();
                    sb.append(ans).append("\n");
                }
            }
            //값 추가 
            else
            {
                pq.add(value);
            }
        }
        
        System.out.println(sb);
    }
}