우선순위 큐(PriorityQueue) compareTo

JAVA에서는 C++에 있는 pair 개념이 없어서 직접 구현해줘야 하고, 정렬(?) 방식도 구현해줘야 한다.

아래 2가지 구조(골격)를 기억하자.

1.

class Pair implements Comparable<Pair> {

}

2.

public int compareTo(Pair p) {

}

-1, -2
-1, -2
1, 2
1, 3
2, 3
3, 42
4, 4
5, -4
6, 4
12, 3
 

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int n;
    static PriorityQueue<Pair> pq = new PriorityQueue<Pair>();
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));                
        
        /*n = Integer.parseInt(br.readLine());

        for(int i=0; i<n; i++) {
            
        }*/
        
        pq.add(new Pair(1, 2));
        pq.add(new Pair(4, 4));
        pq.add(new Pair(2, 3));
        pq.add(new Pair(1, 3));
        pq.add(new Pair(-1, -2));
        pq.add(new Pair(3, 42));
        pq.add(new Pair(5, -4));
        pq.add(new Pair(12, 3));
        pq.add(new Pair(6, 4));
        pq.add(new Pair(-1, -2));
        
        while(!pq.isEmpty()) {
            System.out.println(pq.peek().first + ", " + pq.peek().second);
            pq.remove();
        }
        
        /*bw.flush();
        bw.close();*/
        
    }
}
 
class Pair implements Comparable<Pair> {
    int first, second;
    
    Pair(int f, int s) {
        this.first = f;
        this.second = s;
    }
    
    public int compareTo(Pair p) {
        if(this.first < p.first) {
            return -1; // 오름차순
        }
        else if(this.first == p.first) {
            if(this.second < p.second) {
                return -1;
            }
        }
        return 1; // 이미 this.first가 더 큰 것이 됐으므로, 1로 해준다. -1로
        // -1로 하면 결과가 이상하게 출력됨.
    }
}