[BOJ] 11650, 11651번: 좌표 정렬하기 (Java)

 

🔗 https://www.acmicpc.net/problem/11650

🔗 https://www.acmicpc.net/problem/11651

 

좌표 정렬하기(11650번) 문제는 N개의 좌표를 x좌표가 증가하는 순으로 정렬, 만약 x좌표가 같으면 y좌표가 증가하는 순으로 정렬하는 문제이다.

 

'딱 처음 이 문제를 봤을 때는 merge sort와 같은 정렬 알고리즘을 사용하면 되는건가?'라고 생각해 시도 해봤는데, 한 좌표에는 x값, y값이 모두 있기에 정렬할 시에 코드가 복잡해질 수밖에 없었다. 그리고 에러가 발생하기도 함...

 

당연히 정렬 알고리즘을 쓰겠지라며 생각했던 나는 해답을 찾다 Arrays.sort와 Comparator, Comparable 개념을 접하게 되었다.

이 개념들을 활용하면 아주 간결하게 코드를 짤 수 있었다. 우선 이 낯선 이 개념들을 차근차근 정리해보자.

 

---

Arrays.sort

✔️ Arrays.sort 기본 정렬

Arrays.sort는 Arrays 클래스의 sort 메소드로, 자바에서 배열을 정렬할 때 사용하는 메소드이다. 배열의 요소를 오름차순으로 정렬한다.

int []arr = {5,4,3,2,1};
Arrays.sort(arr);

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

위와 같은 코드의 출력 결과는 1 2 3 4 5 일 것이다.

 

✔️ Comparator를 사용한 Arrays.sort 정렬

또한 sort 메소드를, 다음과 같이 파라미터에 Comparator를 넣어 사용할 수도 있다.

파라미터에 정렬할 요소와 Comparator를 넣은 Arrays.sort() 메소드의 형태

 

💡 Compartor와 Comparable

: 객체끼리 비교하는 데 유용한 인터페이스

Comparator

• compare(T o1, T o2) 메소드 구현 해야 함
• 두 매개변수 객체(o1, o2) 비교

class Product implements Comparator<Product> {
 
	int count;	// 수량
	int price;	// 가격
	
	Product(int count, int price) {
		this.count = count;
		this.price = price;
	}
	
	@Override
	public int compare(Product o1, Product o2) {
    
		// o1의 가격이 o2의 가격보다 크다면 양수
		if(o1.price > o2.price) {
			return 1;
		}
		// o1의 가격이 o2의 가격과 같다면 0
		else if(o1.price == o2.price) {
			return 0;
		}
		// o1의 가격이 o2의 가격보다 작다면 음수
		else {
			return -1;
		}
		
		// 혹은 이렇게
		// return o1.price-o2.price;
	}
}

 

Comparable

• compareTo(T o) 메소드 구현 해야 함
• 자기 자신과 매개변수 객체 비교 → 정수를 반환함
  • 자기 자신 기준으로 상대방과의 차이 값을 비교해 반환.

class Product implements Comparable<Product> {
 
	int count;	// 수량
	int price;	// 가격
	
	Product(int count, int price) {
		this.count = count;
		this.price = price;
	}
	
	@Override
	public int compareTo(Product o) {
    
		// 자기 자신의 count가 o의 count보다 크다면 양수
		if(this.count > o.count) {
			return 1;
		}
		// 자기 자신의 count와 o의 count가 같다면 0
		else if(this.count == o.count) {
			return 0;
		}
		// 자기 자신의 count가 o의 count보다 작다면 음수
		else {
			return -1;
		}
		
		// 혹은 이렇게
		// return this.count-o.count;
	}
}

 

 

=> 정확히는 단지 양수(1), 0, 음수(-1)를 반환하는 게 아니라 대소관계를 나타내는 것

 

그럼 좌표를 어떻게 비교할까?

 

우선 2차원 배열은 1차원 배열들의 set라고 보면 된다.

예를 들어 int[3][2] = {1,2,3,4,5,6}이 있다고 가정하자. 이걸 {(1,2), (3,4), (5,6)}으로 나타낼 수 있으며, 이것은 1차원 배열 3개를 합친 set이라고 볼 수 있겠다. 이 각 1차원 배열을 e1, e2, e3라고 해보자({e1, e2, e3}).

int []e1 = {1,2}이고, e1[0] 즉, 이 배열의 첫 번째 요소(x좌표)는 1이 될 것이다.

 

우리는 e1과 e2의 각 x좌표를 우선 비교하고 싶다. 이걸 두 객체를 비교하는 Comparator 인터페이스의 compare(o1,o2) 메소드로 구현하면

@Override
public int compare(int []e1, int []e2){
	return e1[0] - e2[0];
}

 

이런 식으로 표현할 수 있다.

 

 

문제 조건은 x좌표를 기준으로 점을 오름차순 정렬하고, 만약 x좌표가 같으면 y좌표를 오름차순으로 정렬하라 했기에 if-else문으로 이 조건을 나눠주자.

@Override
public int compare(int []e1, int []e2) {
	if(e1[0] == e2[0])
    	return e1[1] - e[1]; 	// y 좌표 비교
        
    else 
    	return e1[0] - e2[0];	// x 좌표 그냥 비교
}

 

---

 

다시 Arrays.sort()로 돌아가, 위 comparator를 파라미터로 하여 배열을 정렬해보자.

만약 int[5][2]짜리 배열이 있다면,

int [][]arr = new int[5][2];

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

 

여기서 new Comparator<>(){} 부분은 익명 클래스로 쓰였다. (익명 클래스는 클래스의 이름이 없고, 단 하나의 객체만 생성 가능한 클래스라는 특징이 있다.)

💭 내가 착각했던 부분

int [][]arr = new int[5][2];

Arrays.sort(arr, new Comparator<int [][]>() {
	@Override
    public compare(int [][]e1, int [][]e2) {
    	return e1.[0][0] - e2.[1][0];
   	.
        .
        .
    }
});

배열 요소를 비교해야하니까 대충 '이런 식으로 코드를 짜면 되지 않을까?'라며 생각했다.
하지만 이것은 틀렸다! 왜냐하면 Arrays.sort는 1차원 배열을 정렬할 때 사용하는 것이지 2차원 배열 자체를 직접 비교하는 것이 아니기 때문이다.

💡 람다식

위 식을 람다식으로 더 간결하게 정리할 수 있다.

함수 이름을 지정하지 않고 함수를 가독성 좋게, 짧게 만들 수 있는 문법이다. 즉, 함수 이름을 지정하지 않는다는 점에서 익명 클래스로도 변환할 수 있는 것이다. 위 익명 클래스를 람다식으로 짧게 나타내보자.

Arrays.sort(arr, (e1, e2) -> {
	if (e1[0] == e2[0])
    		return e1[1] - e2[1];
    	else
    		return e1[0] - e2[0];
});

 

람다식의 특징

예시

// 메소드
int min(int x, int y) {

    return x < y ? x : y;

}

 

// 람다 표현식

(x, y) -> x < y ? x : y;

• 매개변수(파라미터) 타입을 생략할 수 있다.
• 매개변수가 하나면 괄호도 생략 가능하다.
• 함수 몸체가 명령문 하나로만 이뤄져있다면 중괄호{}도 예시처럼 생략이 가능하다. 

 

결국은 다음과 같은 코드로 정리할 수 있었다.

11650

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

public class BOJ_11650_2 {
    public static void main(String[] args) throws 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 < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

//        for (int i = 0; i < N; i++) {
//            for (int j = 0; j < 2; j++) {
//                arr[i][j] = Integer.parseInt(br.readLine());
//            }
//        }

//        Arrays.sort(arr, new Comparator<int[]>() {
//            public int compare(int[] e1, int[] e2) {
//                if (e1[0] == e2[0])
//                    return e1[1] - e2[1];
//                else return e1[0] - e2[0];
//            }
//        });

        Arrays.sort(arr, (e1, e2) -> {
            if(e1[0] == e2[0])
                return e1[1] - e2[1];

            else return e1[0] - e2[0];
        });

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

 

 

11651번은 11650번과 같은 유형이지만, y좌표로 점을 비교하여 오름차순 정렬하며 만약 두 점의 y좌표가 같다면 x좌표를 기준으로 오름차순 정렬한다는 차이가 있다. 그 점만 유의해서 조건문을 살짝 변형해주면 된다.

11651

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

public class BOJ_11651 {
    public static void main(String[] args) throws Exception{
        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 < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

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

        Arrays.sort(arr, (e1, e2) -> {
            if(e1[1] == e2[1])
                return e1[0] - e2[0];
            else return e1[1] - e2[1];
        });

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

 

 

---

람다식, Comparator, Comparable 모두 나에게 생소한 개념이어서 문제를 쉽게 풀기 어려웠다. 또한, 알고 있다고 생각했던 Arrays.sort는 사실 파라미터로 Comparator를 넣는 형태도 있는 등, 더 다양하다는 점을 발견할 수 있었다.

자바 개념을 더 확실히 꼼꼼히 공부해야함을 뼈저리게 느낄 수 있었다. 파이팅!