algorithm

좌표 정렬 / Comparable, Comparator

juuuuuuun 2024. 8. 26. 23:45

설명

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

 

소스 코드 1

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

//좌표 정렬
public class Main {
    public static int[][] solution(int N, int[][] arr) {
        int[][] tmp = new int[1][2];
        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j < N - 1 - i; j++) {
                if (arr[j][0] > arr[j + 1][0]) {
                    tmp[0][0] = arr[j + 1][0];
                    tmp[0][1] = arr[j + 1][1];
                    arr[j + 1][0] = arr[j][0];
                    arr[j + 1][1] = arr[j][1];
                    arr[j][0] = tmp[0][0];
                    arr[j][1] = tmp[0][1];
                } else if ((arr[j][0] == arr[j + 1][0]) && (arr[j][1] > arr[j + 1][1])) {
                    tmp[0][1] = arr[j + 1][1];
                    arr[j + 1][1] = arr[j][1];
                    arr[j][1] = tmp[0][1];
                }
            }
        }
        return arr;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int arr[][] = new int[N][2];
        for (int i = 0; i < N; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }
        int ans[][] = solution(N, arr);
        for (int i = 0; i < N; i++) {
            System.out.println(ans[i][0]+" "+ans[i][1]);
        }
    }
}

 

소스 코드 2 (Comparable)

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Point implements Comparable<Point>{
    public int x;
    public int y;

    public 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 sc = new Scanner(System.in);
        int N = sc.nextInt();
        ArrayList<Point> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            list.add(new Point(x, y));
        }

        Collections.sort(list);

        for (Point val : list) {
            System.out.println(val.x + " " + val.y);
        }
    }
}

 

Comparble, Comparator 차이점

 - Comparable : 클래스 자체에서 객체의 자연스러운 순서를 정의할 때 사용되고, `compareTo` 메서드를 오버라이드 한다.

 - Comparator : 외부에서 다양한 기준으로 객체를 비교하기 위해 사용되며 `compare` 메서드를 오버라이드 한다.

 

Comparable 인터페이스

 - `compareTo` 메서드 하나만 가지고 있다.

 - `compareTo` 메서드는 현재 객체(this)와 인자로 들어온 책체를 비교한다.

  - 양수 반환 : 현재 객체가 비교 대상보다 뒤에 위치해야 한다.

  - 0 반환 : 두 객체의 순서를 유지한다.

  - 음수 반환 : 현재 객체가 비교 대상보다 앞에 위치해야 한다.

 - `Collections.sort()`를 이용하여 `compareTo()`의 반환값을 통해 객체들의 순서를 조정한다.

 

Comparator 인터페이스

 - `compare` 메서드를 가지고 있다.

 - 클래스에 Comparable을 구현하지 않고 메서드를 만들어서 Comparator를 상속 받고 자기가 원하는 기준을 세워 비교식을 만들 수 있다.

 - 아래와 같이 사용할 수 있다.

List<Person> people = new ArrayList<>();
people.add(new Person("Jun",20));
people.add(new Person("Bae",23));

Comparator<Person> nameComparator = new Comparator<>(){
	@Override
    public int compare(Person p1, Person p2){
    	return p1.name.compareTo(p2.name);
    }
};

Collections.sort(people,nameComparator);

 

 

 

'algorithm' 카테고리의 다른 글

뮤직비디오 (결정 알고리즘) / Arrays.stream()  (1) 2024.08.27
장난꾸러기  (0) 2024.08.24
중복 확인  (0) 2024.08.24
LRU  (0) 2024.08.24
버블 정렬  (0) 2024.08.22