자바 자료구조 우선순위 큐 심화응용 - 내가 원하는 우선순위에 맞는 우선순위 큐를 만드는 방법

1. 원하는 우선순위 기준에 맞는, 우선순위 큐 만들기

 

[(1, 7), (3, 2), (3, 1), (6, 2)] 와 같이 2차 평면상의 점들의 위치가 순서대로 주어졌을 때, 각각의 점의 위치가 주어질 때 마다 지금까지 주어진 점들 중 x, y의 곱이 가장 큰 경우를 출력하는 프로그램을 작성해보세요.

 

위와 같은 문제는 어떻게 해결할 수 있을까?

 

무작정 코드를 작성한다면 점의 위치가 주어질때마다, x*y를 계산하여 최대가 되는 경우를 골라야하므로,

 

$O(N^{2})$이 된다.

 

하지만 PriorityQueue를 이용한다면 순간 최댓값을 찾는 과정이 O(logN)이 되어, 시간복잡도가 O(NlogN)이 된다.

 

그런데, 우선순위 큐를 어떻게 만들어야할까?

 

두 수의 곱이 최대가 되는 특별한 경우를 원하므로, 이 곱이 우선순위가 되어야 한다.

 

자바에서는 custom comparator를 이용해 이 문제를 해결할 수 있다.

 

두 수 x,y를 한번에 관리하는 새로운 클래스 Pair를 정의하고 이 안에 곱을 기준으로 하는 custom comparator를 정의한다.

 

class Pair implements Comparable<Pair> {
    int x,y;

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

    @Override
    public int compareTo(Pair p){
        //x*y 기준으로 내림차순 정렬
        return p.x*p.y - this.x*this.y;
    }
}

 

PriorityQueue의 각 원소가 이렇게 커스텀으로 정의한 Pair를 원소로 갖도록 만들어준다면...

 

Pair에서 정의한 기준으로 알아서 정렬하여 뽑을때마다 항상 x*y가 최대가 되도록 뽑아준다.

 

import java.util.PriorityQueue;

class Pair implements Comparable<Pair> {
    int x,y;

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

    @Override
    public int compareTo(Pair p){
        //x*y 기준으로 내림차순 정렬
        return p.x*p.y - this.x*this.y;
    }
}

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Pair[] points = new Pair[]{
            new Pair(1,7), new Pair(3,2), new Pair(3,1), new Pair(6,2)
        };

        int n = 4;

        PriorityQueue<Pair> pq = new PriorityQueue<>();

        for(int i = 0; i < n; i++){
            pq.add(points[i]); //우선순위 큐에 원소를 넣어주고
            Pair bestP = pq.peek(); //x*y가 가장 큰 경우를 뽑아준다.

            System.out.println(bestP.x + " " + bestP.y);
        }
    }
}

1 7
1 7
1 7
6 2

 

 

이거 알았으면... B형 합격각이었네 ㄹㅇ

 

2. 연습문제

 

2차 평면 위에 서로 다른 위치에 놓여있는 n개의 점이 주어집니다. 이때 원점에서 가장 가까운 점을 하나 골라, 해당 점의 x, y 값에 2씩 더해주는 작업을 m번 반복하려고 합니다. 이를 전부 반복한 이후 원점에 가장 가까이 있는 점을 출력하는 프로그램을 작성해보세요. 원점과 특정 점 (x, y)과의 거리는 ∣x∣+∣y∣ 로 생각하며, 만약 원점과의 거리차 최소인 점이 여러 개 있다면 x값이 가장 작은 점을, 만약 그러한 점이 여러 개라면 y값이 가장 작은 점이 원점과 가장 가까이에 있는 점이라 생각합니다. 단, 같은 지점에 서로 다른 점이 여러 개가 있는 경우는 발생하지 않는다고 가정해도 좋습니다.

 

 

문제 제한이 x,y가 1 이상의 자연수라서 절댓값은 의미가 없다...(이건 좀 아쉽네)

 

x,y를 멤버 변수로 가지는 새로운 class Pair를 정의하고, custom comparator를 정의해준다.

 

두 x,y의 합을 기준으로 오름차순 정렬하는데, 합이 서로 같다면 x값 기준으로 오름차순 정렬하고,

 

x값마저 같다면 y값 기준으로 오름차순 정렬 해준다.

 

이렇게 정의한 Pair를 원소로 가지는 우선순위 큐 PriorityQueue를 정의해주고.. 매 순간 뽑아서, x,y에 각각 2 더해주고

 

다시 우선순위 큐에 넣어준다.

 

m번이 지나고 다시 원소를 뽑으면, 그것이 문제에서 원하는 답

 

import java.util.Scanner;
import java.util.PriorityQueue;

class Pair implements Comparable<Pair>{
    int x,y;

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

    @Override
    public int compareTo(Pair p){

        if(this.x+this.y == p.x+p.y){
            return this.x - p.x;
        } else if(this.x == p.x){
            return this.y - p.y;
        }
        return (this.x+this.y) - (p.x+p.y); 
    }
}

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        PriorityQueue<Pair> pq = new PriorityQueue<>();

        for(int i = 0; i < n; i++){
            pq.add(new Pair(sc.nextInt(), sc.nextInt()));
        }

        for(int i = 0; i < m; i++){

            Pair point = pq.poll();

            point.x += 2;
            point.y += 2;

            pq.add(point);

        }

        Pair point = pq.poll();

        System.out.println(point.x + " " + point.y);


    }
}