자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Sorting and Searching(정렬, 이분검색과 결정알고리즘)_좌표정렬)

 

 

 

7. 좌표 정렬(compareTo)

 

x 좌표 값에 의해 오름차순 정렬하고, x값이 같으면 y값에 의해 오름차순 정렬해서 출력하면 되는 문제

 

예시 입력 1 

5
2 7
1 3
1 2
2 5
3 6

예시 출력 1

1 2
1 3
2 5
2 7
3 6

 

 

아래 코드에 대한 설명

if(this.x==o.x) return this.y-o.y;

 

• 오름차순의 경우 : this - object
• 내림차순의 경우 : object - this

오름차순으로 만들고자할때 현재 메소드를 호출한 this객체가 앞에있고 매개변수로 넘어온 object객체가 뒤에 있다고 생각해라.

이 순서대로 정렬이 되려면 무조건 음수값이 리턴되도록 해야 합니다. 다시말해서 this가 앞에 있고 대상객체가 뒤에 있게 하고, 10 20 이 순서대로 있게 하려면, this에서 object를 빼줘야 합니다.

 

반대로 내림차순으로 만들려고 해도 음수로 만들어줘야 한다. 그때는 object에서 this를 빼줘야 합니다.

강의 풀이 (Time: 170ms Memory: 27MB)

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

// 좌표 하나하나를 저장하는 클래스
class Point implements Comparable<Point> { // Point란 클래스 객체를 정렬한다
    public int x, y;

    // 생성자를 통해 초기화됨
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    // 외워라! - 좌표할땐 이렇게 해라!
    // 오름차순 (this가 앞에 있고, object가 뒤에 있을때 음수 리턴 : 10 20)
    @Override
    public int compareTo(Point o) {
        if (this.x == o.x) return this.y - o.y; // 작은거에서 큰 것 빼기
            // x값이 다르면 x값에 의해 정렬
        else return this.x - o.x;
    }
    // 내림차순 (this가 앞에 있고, object가 뒤에 있을때 음수 리턴 : 20 10)
//    @Override
//    public int compareTo(Point o) {
//        if (this.x == o.x) return o.y-this.y; // 작은거에서 큰 것 빼기
//            // x값이 다르면 x값에 의해 정렬
//        else return o.x-this.x;
//    }
}

public class Main {

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        ArrayList<Point> arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int x = kb.nextInt(); // 2
            int y = kb.nextInt(); // 7
            arr.add(new Point(x, y)); // 포인트 클래스라는 객체 생성해서 List저장
        }
        // 내가 만든 정렬기준으로 정렬됨
        Collections.sort(arr);
        for (Point o : arr) System.out.println(o.x+ " "+o.y);
    }
}

 

// 오름차순 출력
1 2
1 3
2 5
2 7
3 6

// 내림차순 출력
3 6
2 7
2 5
1 3
1 2

 

arr.add(new Point(x, y)); //이부분 출력 - Point클래스에 toString()오버라이딩
System.out.println(arr);
// 출력
[Point{x=2, y=7}]
[Point{x=2, y=7}, Point{x=1, y=3}]
[Point{x=2, y=7}, Point{x=1, y=3}, Point{x=1, y=2}]
[Point{x=2, y=7}, Point{x=1, y=3}, Point{x=1, y=2}, Point{x=2, y=5}]
[Point{x=2, y=7}, Point{x=1, y=3}, Point{x=1, y=2}, Point{x=2, y=5}, Point{x=3, y=6}]

 

 

다른 사람 풀이 1 (Time: 272ms Memory: 32MB)

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Other1 {
    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++)
            for (int j = 0; j < 2; j++)
                arr[i][j] = sc.nextInt();

        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                } else {
                    return o1[0] - o2[0];
                }
            }
        });

        for(int i = 0; i < n; i++){
            System.out.println(arr[i][0] + " "+arr[i][1]);
        }
    }
}

 

 

다른 사람 풀이 2 (Time: 188ms Memory: 27MB)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Other2 {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[][] arr = new int[n][2];
        for (int i = 0; i < arr.length; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        for (int j = 0; j < arr.length; j++) {
            for (int i = 0; i < arr.length; i++) {
                if (arr[i][0] > arr[j][0]) {
                    sort(arr, i, j);
                }
            }
        }

        for (int j = 0; j < arr.length; j++) {
            for (int i = 0; i < arr.length; i++) {
                if (yCondition(arr, i, j)) {
                    sort(arr, i, j);
                }
            }
        }

        for(int i = 0; i < n; i++){
            System.out.println(arr[i][0] + " "+arr[i][1]);
        }
    }

    public static void sort(int[][] arr, int i, int j) {
        int x = arr[i][0];
        int y = arr[i][1];

        arr[i][0] = arr[j][0];
        arr[i][1] = arr[j][1];

        arr[j][0] = x;
        arr[j][1] = y;
    }

    public static boolean yCondition(int[][] arr, int i, int j) {
        return arr[i][0] == arr[j][0] && arr[i][1] > arr[j][1];
    }

}