[백준] 11651 : 좌표 정렬하기2 (JAVA) - 람다식, Comparator

좌표 정렬하기 2

1 초

256 MB

50472

32789

27925

67.339%

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

예제 입력 1

5
0 4
1 2
1 -1
2 2
3 3

예제 출력 1

1 -1
1 2
2 2
3 3
0 4

---

방법 2가지로 풀수 있다.

처음에 그냥 sysout으로 했다가

시간이 극악무도하게 나옴….

방법1

package Day1101;

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

public class B11651_1 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());

		StringTokenizer st;
		int[][] xy = new int[N][2];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			xy[i][0] = Integer.parseInt(st.nextToken());
			xy[i][1] = Integer.parseInt(st.nextToken());
		}

		// 2차원 배열이므로 Arrays.sort 람다식을 이용해야한다.
		// 양수 반환 -> x2 인덱스 0 일때 x1 인덱스 1(또는 양수)
		// 음수 반환 -> x2 인덱스 0 일때 x1 인덱스 -1(또는 음수)
		Arrays.sort(xy, (x1, x2) -> {
			// 만약 y좌표 같으면
			if (x1[1] == x2[1]) {
				return x1[0] - x2[0]; // x 오름차순
			} else {
				return x1[1] - x2[1]; // 아니면 그냥 y만 오름차순
			}
		});

		for (int i = 0; i < N; i++) {
			sb.append(xy[i][0] + " " + xy[i][1]).append("\\n");
		}
		System.out.println(sb);

	}

}

방법2 -Comparator

package Day1101;

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

public class B11651_2 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());

		StringTokenizer st;
		int[][] xy = new int[N][2];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			xy[i][0] = Integer.parseInt(st.nextToken());
			xy[i][1] = Integer.parseInt(st.nextToken());
		}

		// 함수형 인터페이스 Comparator 의 메서드 compare(e1,e2)
		// 양수 반환 -> e1 인덱스 1 e2 인덱스 0
		// 음수 반환 -> e1 인덱스 -1 e2 인덱스 0
		Arrays.sort(xy, new Comparator<int[]>() {

			@Override
			public int compare(int[] x1, int[] x2) {

				// 만약 y좌표 같으면
				if (x1[1] == x2[1]) {
					return x1[0] - x2[0]; // x 오름차순
				} else {
					return x1[1] - x2[1];
				}
			}

		});

		for (int i = 0; i < N; i++) {
			sb.append(xy[i][0] + " " + xy[i][1]).append("\\n");
		}
		System.out.println(sb);

	}

}

위에서부터 1번방식 - 2번방식 순서이다.

Comparator쓰는게 좀 더 빠르다

---

왜틀렸을까!

첫시도 - 틀린코드

package Day1101;

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

public class B11651 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		StringTokenizer st;
		int[][] xy = new int[N][2];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			xy[i][0] = Integer.parseInt(st.nextToken());
			xy[i][1] = Integer.parseInt(st.nextToken());
		}

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

	}

}

Exception in thread "main" java.lang.ClassCastException: class [I cannot be cast to class java.lang.Comparable ([I and java.lang.Comparable are in module java.base of loader 'bootstrap')
	at java.base/java.util.ComparableTimSort.countRunAndMakeAscending(ComparableTimSort.java:320)
	at java.base/java.util.ComparableTimSort.sort(ComparableTimSort.java:188)
	at java.base/java.util.Arrays.sort(Arrays.java:1041)
	at Day1101.B11651.main(B11651.java:25)

 

쉬운줄알았지…………………………………………………………..

1차원 배열은 Arrays.sort(배열이름)으로 쉽게 정렬할 수 있다.

하지만 2차원 이상의 배열일 경우엔 위와 같은 오류가 난다..

그래서 람다식이라는 것을 이용해야 한다고 한다.

 

 

람다식(Lambda Expressions)

메서드를 하나의 식(expression)으로 표현한 것!

메서드를 람다식으로 표현하면 메서드 이름과 반환값이 없어지므로 **익명 함수(anonymous function)**라고도 부른다.

특히 메서드가 1번만 사용되고 메서드 길이가 짧은 경우 매우 유용하다.

자바에서 메서드(함수)는 혼자서 생존할 수 없다. 객체가 아니기 때문에 클래스도 만들어야 하고, 객체도 생성해야 쓸 수 있다. 하지만 람다식으로 인해 변수처럼 스스로 존재하며 매개변수로 전달하거나 결과로 반환될 수 있다.

즉, 람다식으로 메서드(함수)는 객체로 취급된다는 말이다.

public class sortTest {
	public static void main(String[] args) {
		int[][] arr = {{3,5},{2,7},{1,6}};
        
		// 정렬
		Arrays.sort(arr, (num1, num2) -> {
			return Integer.compare(num1[0], num2[0]);
		});
	}
}

배열을 정렬할 때, 비교 요소를 첫 번째 요소로 정하겠다는 의미이다.

comparator에 내부 함수를 이용해서 더 간단하게도 가능하다.

Arrays.sort(arr, Comparator.comparingInt(num1 -> num1[0]));

/ 1. Comparator 익명 클래스 구현
Arrays.sort(arr, new Comparator<int[]>() {
    @Override
    public int compare(int[] o1, int[] o2) {
        return o1[0]-o2[0]; // 첫번째 숫자 기준 오름차순 {1,30}{2,10}{3,50}{4,20}{5,40}
        //return o2[0]-o1[0]; // 첫번째 숫자 기준 내림차순 {5,40}{4,20}{3,50}{2,10}{1,30}
        //return o1[1]-o2[1]; // 두번째 숫자 기준 오름차순 {2,10}{4,20}{1,30}{5,40}{3,50}
        //return o2[1]-o1[1]; // 두번째 숫자 기준 내림차순 {3,50}{5,40}{1,30}{4,20}{2,10}
    }
});

본 코드에 적용해보면

// 정렬 - (1)
		Arrays.sort(xy, (x1, x2) -> {
			return Integer.compare(x1[0], x2[0]);
		});
		
		// 정렬 - (2)
		Arrays.sort(xy, Comparator.comparingInt(x1 -> x1[0]));

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

 

 

 

두번째 요소를 정렬하려면

public class sortTest {
	public static void main(String[] args) {
		int[][] arr = {{3,5},{2,7},{1,6}};
        
		// 정렬 - (1)
		Arrays.sort(arr, (num1, num2) -> {
			return Integer.compare(num1[1], num2[1]);
		});
		// 정렬 - (2)
		Arrays.sort(arr, Comparator.comparingInt(num1 -> num1[1]));
	}
}