문제
2차원 평면 위의 점 N개를 y좌표 기준 오름차순으로 정렬하고, y좌표가 같으면 x좌표 기준 오름차순으로 정렬하여 출력하는 문제다.
입력
- 첫째 줄: 점의 개수 N (1 이상 100,000 이하)
- 둘째 줄부터 N개 줄: 각 점의 x좌표, y좌표 (절댓값 100,000 이하의 정수)
출력
N개의 줄에 정렬된 점을 순서대로 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 0 4 1 2 1 -1 2 2 3 3 | 1 -1 1 2 2 2 3 3 0 4 |
풀이
y좌표를 1차 기준, x좌표를 2차 기준으로 하는 커스텀 비교자를 이용한 정렬로 문제를 해결한다.
- N개의 좌표를
int[N][2]배열에 저장한다. Arrays.sort에 람다 비교자를 전달한다.- y좌표(
[1])가 다르면 y 오름차순, 같으면 x좌표([0]) 오름차순으로 정렬한다. - 정렬된 배열을 순서대로 출력한다.
핵심 아이디어: Arrays.sort의 2차원 배열 정렬 시 람다를 사용해 다중 조건 비교자를 간결하게 표현한다. y 우선 정렬이므로 e1[1] - e2[1]을 먼저 비교하고, 같을 때만 e1[0] - e2[0]을 비교한다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Day05BOJ11651좌표정렬하기2 { // 11651번 좌표 정렬
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[1] == e2[1]) {
return e1[0] - e2[0];
} else {
return e1[1] - e2[1];
}
});
for (int n = 0; n < N; n++) {
System.out.println(arr[n][0] + " " + arr[n][1]);
}
}
}복잡도
- 시간: O(N log N) —
Arrays.sort의 비교 정렬 - 공간: O(N) — 좌표 저장 배열