백준 11650번, 11651번 -좌표 정렬하기(JAVA)

11651번과 11650번 유사한 유형이라 두 문제풀이를 같이 올립니다.

정답률이 높은 문제지만 아직 코딩테스트 초보자라 어려웠네요..

다른 분들의 답을 참고해서 제가 이해한 내용을 바탕으로 최대한 상세하게 작성해봅니다.

 

 

 

-11650번

www.acmicpc.net/problem/11650

11650번: 좌표 정렬하기

제가 쓴 코드 입니다.

 

 

 

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

public class Main {
    public static void main(String[] args){
        // 11650
        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, new Comparator<int[]>() {
            @Override
            public int compare(int[] x, int[] y) {
                if(x[0]==y[0]){
                    return Integer.compare(x[1],y[1]);
                }
                return Integer.compare(x[0],y[0]);
            }
        });

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

        sc.close();
    }
}

 

풀이 과정

Arrays.sort와 Comparator를 응용합니다.

이 둘에 대한 이해에는 아래 주소의 글들이 도움이 되었습니다.

 

https://jamesdreaming.tistory.com/65

[자바 코딩] 배열 정렬 Arrays.sort()

https://gmlwjd9405.github.io/2018/09/06/java-comparable-and-comparator.html

[Java] Comparable와 Comparator의 차이와 사용법 - Heee's Development Blog

 

기본적으로 x좌표 기준으로 오름차순으로 정렬하되, 비교할 x좌표가 같을 경우에는 y좌표가 오름차순 되어야 합니다.

 

1. 우선 점 개수 N을 받고, N길이의 2차원 배열 arr를 생성합니다.

2. 첫번째 반복문에서 점의 좌표를 입력 받습니다.

3. Arrays.sort 메소드 사용.

   이때, 기본정렬인 오름차순이 아닌, x좌표의 값이 같을 경우에는 y좌표가 오름차순 되도록 해야하므로

   

   Arrays.sort의 두번째 매개변수로 Comparator 인스턴스를 생성과 동시에 익명 인터페이스를 구현하고,

   compare메소드를 오버라이딩 합니다.

 

*compare(T o1, T o2) 의 기본 원리

 - o1 < o2   : 음수 리턴

 - o1 == o2 : 0 리턴

 - o1 > o2   : 양수 리턴

즉, compare가 반환하는 값에 따라 정렬이 됩니다. (기본 오름차순)

 

Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] x, int[] y) {
                if(x[0]==y[0]){
                    return Integer.compare(x[1],y[1]);
                }
                return Integer.compare(x[0],y[0]);
            }
        });

compare의 매개변수에 들어가는 int[] x와 int[] y는

만약 비교할 두 점의 좌표가 (a,b) (c,d) 로 들어온다면

int[] x = {a,b}   int[] y = {c,d}  와 같이 각각의 1차원 배열이 됩니다.

 

기본적으론 return Integer.compare(x[0],y[0]); 가 수행됩니다.

(이때 사용되는 compare는 Integer의 compare 입니다. x좌표끼리 비교한 결과가 int로 반환됩니다.)

 

x좌표가 같을 경우는 (x[0]==y[0])

return Integer.compare(x[1],y[1]);

y좌표를 기준으로 비교, 오름차순이 수행됩니다.

 

4. 정렬 후엔 출력 양식에 맞게 arr가 출력되도록 한 뒤, Scanner를 닫아줍니다.

 

 

-11651번

 

www.acmicpc.net/problem/11651

11651번: 좌표 정렬하기 2

 

제가 쓴 코드 입니다.

 

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

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

        //백준 11651번
        
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // N개의 점
        int[][] arr = new int[N][2]; // (x,y)이므로 N개의 점이 2묶음씩, 이차원 배열

        for(int i=0; i<N; i++) {
            arr[i][0] = sc.nextInt();	// X좌표
            arr[i][1] = sc.nextInt();	// Y좌표
        }       

        Arrays.sort(arr, new Comparator<int[] >() {
            @Override
            public int compare(int[] x, int[] y) {

                if(x[1] == y[1]) {    // Y좌표가 동일할 경우에는 X좌표 순으로 정렬
                    return Integer.compare(x[0], y[0]); 
                }
                return Integer.compare(x[1], y[1]);	// 기본적으로 Y좌표 오름차순으로 정렬
            }
        });

        // x y 형태로 2차원배열 출력
        for(int i=0; i<N; i++) {
            System.out.println(arr[i][0] + " " + arr[i][1]);

        }
        sc.close();


    }
}

 

위와 동일한 유형입니다.

여기선 기본적으로 y좌표 기준으로 오름차순으로 정렬, y좌표가 동일할 경우엔 x좌표 기준 오름차순으로 정렬됩니다.