백준 11279 최대 힙 [JAVA]

Ga0·2025년 1월 31일

baekjoon

목록 보기

143/146

문제해석

입력받을 연산의 개수(=N)개를 입력받고 N개만큼 자연수나 0을 입력받아 연산을 처리한다.
- 0을 입력받은 경우 배열에서 가장 큰 값을 출력 후 그 값을 배열에서 제거하고 만약 배열이 비어있다면 0을 출력한다.
- 자연수를 입력받은 경우는 배열에 해당 자연수(x)를 추가한다.
문제를 풀기 앞서, 큐(Queue)와 우선순위 큐(PriorityQueue)를 알아야 한다.

큐(Queue)

각 네모안의 숫자는 우선순위라고 가정하자.

일반 큐(Queue)는 우선순위를 고려하지 않고 FIFO(선입선출) 방식으로 가장 처음으로 들어간 것이 나오는 구조다.

데이터를 추가(Enqueue)했을 때 rear(맨 뒤) 부분에 데이터가 추가되고 rear이 다시 추가된 위치로 조정된다.

데이터를 추출(Dequeue)했을 때 front(맨 앞) 부분의 데이터가 추출되고 front부분이 뒤의 데이터의 위치로 조정된다.

우선순위 큐(PriorityQueue)

각 네모안의 숫자는 우선순위라고 가정하자.

우선순위 큐(PriorityQueue)는 우선순위 포인터(highest priority)를 가지고 있어서 우선순위가 높은 것 부터 추출된다.

데이터를 추가(Enqueue)했을 때 rear(맨 뒤) 부분에 데이터가 추가되고 rear이 다시 추가된 위치로 조정되며, highest priority가 조정된다.

데이터를 추출(Dequeue)했을 때 front(맨 앞) 부분의 데이터가 추출되고 front부분이 뒤의 데이터의 위치로 조정되며, highest priority가 조정된다.

그렇다면, 우선순위가 동일한 경우는 어떤 것을 먼저 추출해야할지 의문일 수도 있다.

그러한 경우에는 가장 먼저 들어온 데이터 먼저 추출한다. (FIFO 구조이기 때문!)

우선순위 높은 순 or 낮은 순


/* 위의 예시는 높은 우선순위먼저 나오도록 예시를 들었지만 낮은 순인지 높은 순인지는 아래와 같이 선언해서 사용해야한다. */

// default : 우선순위가 낮은 숫자가 먼저 나온다. (낮은 숫자 순)
PriorityQueue<Integer> pQ = new PriorityQueue<>();
 
// 우선순위가 높은 숫자가 먼저 나온다. (높은 숫자 순)
PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());

코드

틀린 코드 (시간 초과)

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine()); //연산 개수
        ArrayList<Integer> Queue = new ArrayList<>();

        while(N --> 0){
            int x = Integer.parseInt(br.readLine()); //연산
            if(x == 0){ //0이면 가장 큰 값을 출력하고 배열에서 제거
                if(Queue.size() == 0){ //배열이 비어있으면 0을 출력
                    sb.append(0).append("\n");
                }else{ //배열이 안비어있으면
                    Integer max = Collections.max(Queue);
                    sb.append(max).append("\n");
                    Queue.remove(max);
                }
            }else{ //0이 아니고, 자연수라면 배열에 x를 추가
                Queue.add(x);
            }
        }
        br.close();
        System.out.println(sb);
    }
}

맞은 코드

import java.io.*;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine()); //연산 개수
        /*
        	우선순위 큐를 사용 
        	Collections.reverseOrder() -> 우선순위가 높은 숫자가 먼저 나옴 : 큰 숫자
        */
        PriorityQueue<Integer> Queue = new PriorityQueue <>(Collections.reverseOrder());

        while(N --> 0){
            int x = Integer.parseInt(br.readLine()); //연산
            if(x == 0){ //0이면 가장 큰 값을 출력하고 배열에서 제거
                if(Queue.isEmpty()){ //배열이 비어있으면 0을 출력
                    sb.append(0).append("\n");
                }else{ //배열이 안비어있으면
                    sb.append(Queue.poll()).append("\n");
                }
            }else{ //0이 아니고, 자연수라면 배열에 x를 추가
                Queue.add(x);
            }
        }
        br.close();
        System.out.println(sb);
    }
}

일반적인 큐는 먼저 들어간 데이터가 먼저 나가는 구조인 FIFO 형식의 자료구조이다.
반면에 우선순위 큐의 경우 들어가는 순서와는 상관없이 우선순위가 높은 데이터(큰 숫자)가 먼저 나가는 자료구조이다.
처음에는 그냥 일반적인 queue 느낌으로 사용해서 0이라는 숫자가 입력되면 그때마다 max값을 찾아서 출력하고 지워서 시간초과가 난 것 같다.