[Java] 우선순위 큐와 compareTo() 오버라이드 (백준 11650 예시)

백준 11650 좌표정렬하기 문제를 풀면서 새롭게 공부한 내용을 정리하기 위해 포스팅한다.

 

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

11650번: 좌표 정렬하기

대충 문제를 보면

입력으로 x, y좌표들 받기

출력으로 정렬된 좌표들을 출력하는데, x좌표 오름차순으로 정렬하되 x좌표 값이 같다면 y좌표  오름차순으로 정렬한다.

 

처음에는 구현하기 쉬운 버블정렬을 사용해서 만들어봤지만 예상대로 시간초과

 

그래서O(nlogn)인 힙정렬을 사용하기로 했다.

 

코드를 작성하다가 문득 이런 생각이 들었다.

클래스 만드는게 재밌어서 자바를 좋아했는데 문제 풀면서 클래스를 새로 만든적이 없네??

생각이 들자 마자 마침 좌표값 2개가 있으니 클래스를 만들기로 했다.

 

* 힙정렬 코드

먼저 자바에서 쉽게 사용할 수 있는 힙정렬 코드를 보자.

static void heapSort(int []arr) {
        // 만약 높은숫자가 우선순위라면 매개변수로 Collections.reverseOrder() 추가
        PriorityQueue<Integer> heap = new PriorityQueue<>();

        // 배열 힙에 넣기
        for(int i = 0; i < arr.length; i++) {
            heap.add(arr[i]);
        }

        // 힙에서 우선순위 가장 낮은 값 원소(root노드) 하나씩 뽑기
        for(int i = 0; i < arr.length; i++) {
            arr[i] = heap.poll();
        }
    }

위 코드는 백준 2751에서 사용한 코드이다.

 

public class에서 바로 사용하려고 static이 붙은 메소드이다.

매개변수로 int형 배열을 받아오고 우선순위 큐(PriorityQueue)를 만든다.

우선순위 큐에 들어갈 애의 타입은 Integer다.

우선순위 큐는 이름대로 우선순위가 중요할 때, 원하는 기준을 두고 삽입 시 정렬이 자동으로 이루어진다.

이 때 정렬이 힙을 사용한 힙정렬을 쓰는데, 힙정렬의 시간복잡도가 O(nlogn)이다.

 

다음 for문으로 받아온 배열을 아까 만든 큐에 차례로 집어넣는다. add()메소드를 사용하면 된다.

 

다름 poll()을 사용해서 루트노드부터 뽑아서 배열에 순서대로 집어넣는다.

얕은복사로 매개변수로 배열을 받아왔기 때문에 배열에 그대로 집어넣으면 힙정렬 메소드를 호출한 메소드의 배열에 그대로 저장된다. 그래서 따로 리턴하지 않는다.

 

* 클래스 작성

class Points implements Comparable<Points> {
    private int x;
    private int y;

    public Points(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return this.x;
    }
    public int getY() {
        return this.y;
    }

    @Override
    public int compareTo(Points p) {
        if(this.x > p.getX()) {
            return 1;
        }
        else if(this.x < p.getX()) {
            return -1;
        }
        else if(this.x == p.getX()) {
            if(this.y > p.getY()) {
                return 1;
            }
            else if(this.y < p.getY()) {
                return -1;
            }
        }

 

문제에서 x좌표와 y좌표를 입력하고, 이 좌표를 기준으로 정렬을 해야 하기 때문에 Points라는 클래스를 만들어 멤버변수로 x, y를 만들었다.

 

클래스 이름 다음에 implements 키워드를 사용했는데, 이것은 부모클래스에 선언되어있는 것을 자식클래스에서 정의할 때 사용하는 키워드이며, 이것을 "인터페이스를 구현한다." 라고 한다.

즉, 부모클래스에서는 형태만 선언, 자식클래스에서 오버라이드(구현)하는 것이다.

따라서 위의 코드에 따르면 Comparable이라는 인터페이스(부모)에 정의된 것을 Points클래스(자식)에서 오버라이드 해야한다. 오버라이드 할 것은  compareTo()라는 메소드이고, 해당 메소드를 사용할 타입이 우리가 만들 Points라는 클래스타입인 것이다.

 

같은 이름을 가진 메소드를 만드는 것이기에 함수중복과 헷갈릴 수 있는데, 함수 중복은 매개변수가 다른, 이름이 같은 함수를 만드는 것이고, 오버라이드는 부모가 선언한 것을 자식이 필요한 용도에 맞게 만들어내는 것이다.

 

생성자로 Points객체를 만들 때 x, y값을 초기화하도록 한다.

 

멤버변수의 접근지정자가 private이므로 getX() getY()라는 메소드를 만들어서 해당 메소드로 값에 접근할 수 있게 한다.

 

다음이 중요한 compareTo()를 오버라이드 하는 부분이다.

VSCode를 사용한다면 컨트롤 + 스페이스바 누르면 추천하는 것들이 나오는데, 오버라이드 해야 할 것들이 나온다. compareto()를 선택하면 부모가 선언해놓은 모양새가 나오고 여기서 정의할 수 있다.

아니면 공식 문서같은것을 찾아보면 어떻게 사용해야하는지 자세히 알 수도 있다.

 

implements키워드를 사용할 때 Points타입이라고 명시 해 주었기에 매개변수로 Points를 받는다.

compareTo()를 사용해서 비교할 때, 크면 1, 작으면 -1을 리턴해준다.

이에 맞게 해당 메소드 안에 문제에서 준 조건대로 코딩을 해 준다.

x가 비교할 대상보다 크면 1, 작으면 -1

x가 같다면 y를 비교해서 y가 크면 1, 작으면 -1을 리턴하게 한다.

 

이렇게 하면 해당 클래스를 정렬시킨다면 위에 만들어둔 조건대로 정렬하게 된다.

 

이제 위에서 본 힙정렬 코드에 적용시켜보자.

 

* 메소드 작성

// 힙정렬 사용
    static Points []sortPoints(int []x, int []y) {
        PriorityQueue<Points> pointsHeap = new PriorityQueue<>();
        
        int count = x.length;
        Points [] points = new Points[count];

        for(int i = 0; i < count; i++) {
            pointsHeap.add(new Points(x[i], y[i]));
        }

        for(int i = 0; i < count; i++) {
            points[i] = pointsHeap.poll();
        }

        return points;
    }

위에서 본 것과 크게 다르지 않다.

우선순위 큐를 만드는데, Points클래스를 담는 우선순위 큐를 만들었다.

위에 설명한 대로 우선순위 큐 특성상 원소를 삽입하면 자동으로 힙정렬이 된다.

 

첫 번째 for문에서 우선순위 큐에 Points객체를 만들어 넣는데, 위에서 구현한 대로 생성자가 작동되며 x, y값이 초기화된다.

큐에 객체를 집어넣을 때마다 Points클래스에 오버라이드 했던 compareTo()가 실행되어 x좌표와 y좌표를 기준으로 정렬시킨다.

 

저렇게 큐에 집어넣기만 해도 원하는 기준으로 정렬이 된다.

 

이후 정렬된 객체를 리턴하고 main메소드에서 해당 객체를 출력하면 문제를 해결할 수 있다.

 

* 코드 전체

// 좌표 정렬하기 11650
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Points implements Comparable<Points> {
    private int x;
    private int y;

    public Points(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return this.x;
    }
    public int getY() {
        return this.y;
    }

    @Override
    public int compareTo(Points p) {
        if(this.x > p.getX()) {
            return 1;
        }
        else if(this.x < p.getX()) {
            return -1;
        }
        else if(this.x == p.getX()) {
            if(this.y > p.getY()) {
                return 1;
            }
            else if(this.y < p.getY()) {
                return -1;
            }
        }

        return 0;
    }
}

public class P_11650 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int input = Integer.parseInt(br.readLine());
        int []x = new int[input];
        int []y = new int[input];

        for(int i = 0; i < input; i++) {
            st = new StringTokenizer(br.readLine());
            x[i] = Integer.parseInt(st.nextToken());
            y[i] = Integer.parseInt(st.nextToken());
        }

        Points []points = sortPoints(x, y);

        for(int i = 0; i < input; i++) {
            sb.append(points[i].getX() + " " + points[i].getY() + "\n");
        }
        bw.write(sb.toString());
        bw.flush();

        br.close();
        bw.close();
    }

    // 힙정렬 사용
    static Points []sortPoints(int []x, int []y) {
        PriorityQueue<Points> pointsHeap = new PriorityQueue<>();
        
        int count = x.length;
        Points [] points = new Points[count];

        for(int i = 0; i < count; i++) {
            pointsHeap.add(new Points(x[i], y[i]));
        }

        for(int i = 0; i < count; i++) {
            points[i] = pointsHeap.poll();
        }

        return points;
    }
}

 

이렇게 하면 11651번 문제도 오버라이드 부분만 살짝 바꿔주면 똑같이 풀 수 있다.