[JAVA11/알고리즘] 6-7 좌표 정렬

 💬 문제

N개의 평면상의 좌표(x, y)가 주어지면 모든 좌표를 오름차순으로 정렬하는 프로그램을 작성하세요.

정렬기준은 먼저 x값의 의해서 정렬하고, x값이 같을 경우 y값에 의해 정렬합니다. 

 

🔨 입력

첫째 줄에 좌표의 개수인 N(3<=N<=100,000)이 주어집니다.

 

두 번째 줄부터 N개의 좌표가 x, y 순으로 주어집니다. x, y값은 양수만 입력됩니다.

 

 

🔨출력 

N개의 좌표를 정렬하여 출력하세요.

 

 

👊🏻 예시 입력 1 

5
2 7
1 3
1 2
2 5
3 6

👊🏻 예시 출력 1

 

1 2
1 3
2 5
2 7
3 6

 

💡 해결

이 문제를 풀면서 새로 알게된 점이 많아서 남긴다.

 

처음에 coordinate라는 구조체를 만들어서 풀려고 했다.

생각보다 까다로워져서 구글링을 하던 도중 자바에는 Point라는 클래스를 지원한다는 것을 알았다.

 

class Point implements Comparable<Point> {
    public int x, y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }

필드에는 x좌표, y좌표가 존재한다.

밑에 생성자도 지정해주었다. 

 

문제에서 x좌표,y좌표에 대해서 오름차순으로 정렬하도록 요구하였다.

그러기 때문에 sort함수를 쓸건데, compareTo 함수를 오버라이드 하기위해서 Comparable<Point> 인터페이스를 상속받았다.

 @Override
    public int compareTo(Point o) {
        if (this.x == o.x) return this.y - o.y;
        else return this.x - o.x;
    }

  위는 compareTo 함수를 오버라이드 해준것이다.

 

문제에서 x좌표를 우선으로 정렬하고 다음으로 y좌표에 따라서 정렬해주기때문에

위와 같이 코드를 짰다.

 

다른것은 입력받은 좌표들을 Point 클래스로 만들어 주고, ArrayList에 넣어 정렬만 해주면된다.

여기서 아까 compareTo를 오버라이드 했기때문에, 문제에서 요구하는 대로 정렬이 된다. 

👨🏻‍💻  CODE

import java.util.*;

class Point implements Comparable<Point> {
    public int x, y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Point o) {
        if (this.x == o.x) return this.y - o.y;
        else return this.x - o.x;
    }


}

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        ArrayList<Point> arr = new ArrayList<>();
        for(int i=0; i<n; i++){
            int x = in.nextInt();
            int y = in.nextInt();
            arr.add(new Point(x,y));
        }
        Collections.sort(arr);
        for(Point o : arr){
            System.out.println(o.x+" "+o.y);
        }
    }
}

 

 

💪🏻 결과