백준 11650 좌표 정렬하기 자바 java

 

이차원 배열을 정렬하는 문제라고 볼 수 있다.

 

N개의 (x, y)를 정렬하는 것이다.

 

x를 기준으로 우선 정렬하고, x값이 같다면 y를 사용하여 정렬하라는 것이다.

 

일단 속도를 무시하고 직접적인 방식으로 풀어보았다.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {


        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();
        }
        // 여기까지 입력받는 코드

        for (int i = 0; i < N - 1; i++) {
            if (arr[i][0] > arr[i + 1][0]) {
            // i번째 x와 i+1번째 x가 같다면,
            
                int[] tmp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tmp;
                //이런식으로 일차원 배열을 다른 배열에 통째로 넣어 자리를 바꾼다.
                
            }

            else if (arr[i][0] == arr[i + 1][0]) {
                if (arr[i][1] > arr[i + 1][1]) {
                    int[] tmp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = tmp;
                }
                //아래도 마찬가지이다.
            }
        }

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < 2; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }

        sc.close();
    }

}

 

 

하지만 이 방식은 모든 경우의 수를 비교하는 버블정렬방식이다.

 

버블정렬은 시간복잡도가 O(n^2)로 n이 커질 수로 연상해야하는 양이 기하급수적으로 많아진다.

 

따라서 위 방식을 사용하면 시간초과가 발생할 것이다.

 

 

그렇다면 효율성이 좋은 Arrays.sort()를 사용한다.

 

하지만 Arrays.sort()는 일차원 배열만 정렬한다. 

 

람다식을 통해 해결해 본다.

 

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

public class Main {
    public static void main(String[] args) throws Exception {

        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();
        }

        Arrays.sort(arr, (e1, e2) -> {
            /*
             * 시간초과를 막기위해 Arrays.sort를 사용하지만, 일차원 배열만 정렬할 수 있다.
             * 그렇기 때문에 일차원 배열처럼 사용하는 것이 중요하다.
             * 
             * 람다식을 사용한다. arr은 arr[][]의 일차원 배열만 나타낸다. arr[0]은 {1, 2}식
             * e1은 arr[][]의 {1,2}를 의미한다.
             * 즉 arr을 일차원형태로 불러오겠고, 이차원 내부의 모양은 {e1, e2} 처럼
             * 정의되어있다는 것을 타나낸다.
             */

            if (e1[0] == e2[0]) {
                // arr[i][0]과 arr[i + 1][0]이 같다면과 같의 의미이다.
                return e1[1] - e2[1];
                // arr[i][1]과 arr[i + 1][1]을 비교하라는 의미이다.
                // e1[1] - e2[1];하는 이유는 Arrays.sort가 어떤 것이 더 큰지 확인하기 위함이다.

            } else {
                return e1[0] - e2[0];
                // arr[i][0]과 arr[i + 1][0]이 다르다면
                // arr[i][0]과 arr[i + 1][0]을 비교하라는 의미이다.
            }

        });

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

        sc.close();
    }

}

 

 

그렇다면 효율성이 좋은 Arrays.sort()를 사용한다.

 

하지만 Arrays.sort()는 일차원 배열만 정렬한다.