99클럽 코테 스터디 10일차 TIL [PriorityQueue]

- 오늘의 학습 키워드 : PriorityQueue (내림차순)

[문제 이름 : 최대 힙  (백준, S2) ]

문제 url : https://www.acmicpc.net/problem/11279

 

내가 작성한 코드는 아래와 같다.

import java.util.*;
import java.io.*;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i=0; i<n; i++) {
            solution(Integer.parseInt(br.readLine()));
        }
        System.out.println(sb.toString());
    }
    
    static void solution(int num) {
        if(num == 0) {
            int returnNum = pq.isEmpty() ? 0 : pq.poll();
            sb.append(returnNum).append("\n");
        } else {
            pq.add(num);
        }
    }
}

 

최대 힙의 개념을 알고 있던 상태라, 쉽게 문제를 풀 수 있었다.

x에 0이 들어왔을 때, PriorityQueue가 비어있는지 여부에 따라 결과값을 다르게 출력해주었다.

 

풀이 시간 : 5분

 

[추가 공부 : PriorityQueue 원하는 항목대로 정렬하기]

PriorityQueue를 사용하면서, 사용자가 원하는 형식으로 정렬을 하려면 어떻게 해야 하는지 알아보겠다.

위의 코드에서 처럼, 만약 내림차순과 같은 형태로 정렬을 해주고 싶다면, Collections.reverseOrder();를 사용해 순서를 거꾸로 바꿔주면 된다. 그러나, 가끔 문자열의 2번째 자리로 정렬을 하거나, 특정 문자열 위치를 기준으로 정렬하고 싶을 때는 Comparator를 사용하면 된다.

import java.util.*;
import java.io.*;
public class Main {
    static StringBuilder sb = new StringBuilder();
    static PriorityQueue<String> pq;

    public static void main(String[] args) throws IOException {
        // Comparator 선언
        pq = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                // 두 번째 문자 기준으로 정렬하려는 경우
                if (s1.charAt(1) < s2.charAt(1)) return -1;
                else if (s1.charAt(1) > s2.charAt(1)) return 1;
                else return 0;

                // 오름차순인 경우, return o1.compareTo(o2); 을 작성한다.
                // 내림차순인 경우, return o2.compareTo(o1); 을 작성한다.
            }
        });

        // 이후, poll()이나 remove()를 사용하여 정렬된 문자열 객체를 가져오면 된다.
    }
}

 

내일은 금융 공기업 취업을 위해, 금융 시사 상식에 대해 공부해보려 한다.