문제
2차원 평면 위의 점 N개를 x좌표 오름차순으로, x좌표가 같으면 y좌표 오름차순으로 정렬해 출력하는 문제다.
입력
- 첫째 줄: N
- 이후 N개 줄: x좌표와 y좌표
출력
정렬된 좌표를 한 줄에 하나씩 출력
예제
| 입력 | 출력 |
|---|---|
5 3 4 1 1 1 -1 2 2 3 3 | 1 -1 1 1 2 2 3 3 3 4 |
풀이
2차원 배열에 좌표를 저장하고, x좌표를 1차 기준, y좌표를 2차 기준으로 하는 Comparator를 사용해 정렬한다. Java 8의 람다 표현식으로 간결하게 작성할 수 있다.
int[N][2]배열에 N개의 좌표를 저장한다.Arrays.sort에 람다 Comparator를 전달한다: x가 다르면 x 오름차순, x가 같으면 y 오름차순.- 정렬 결과를 순서대로 출력한다.
핵심 아이디어: 다중 키 정렬은 1차 조건이 같을 때 2차 조건으로 비교하는 Comparator로 구현한다. 버블 정렬은 O(N^2)으로 N=100,000에서 시간 초과가 발생하므로 Java의 Arrays.sort(O(N log N))을 사용해야 한다.
코드
package ASP_study.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Day04BOJ11650좌표정렬하기 { // 11650번 좌표 정렬
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int N = Integer.parseInt(br.readLine());
int[][] arr = new int[N][2];
for (int num = 0; num < N; num++) {
st = new StringTokenizer(br.readLine());
arr[num][0] = Integer.parseInt(st.nextToken());
arr[num][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr, (e1, e2) -> {
if(e1[0] == e2[0]) {
return e1[1] - e2[1];
} else {
return e1[0] - e2[0];
}
});
/* // 아직 우리가 배운 걸로는 시간초과가 뜨는 자바 비친화적인 문제.
for (int i = N - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j][0] > arr[j + 1][0]) {
int[] temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
} else if (arr[j][0] == arr[j + 1][0]) {
if (arr[j][1] > arr[j + 1][1]) {
int[] temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
*/
for (int n = 0; n < N; n++) {
System.out.println(arr[n][0] + " " + arr[n][1]);
}
}
}복잡도
- 시간: O(N log N)
- 공간: O(N)