백준 11650 좌표 정렬하기 [JAVA]

리뷰

시간초과

• 2차원 배열로 값을 입력받은 후, 반복문을 돌려서 모든 값을 하나씩 비교했다. 

 

공부한 것

• 1차원 배열 정렬 시 사용하는 Arrays.sort(arr)의 인자로 Comparator인터페이스의 Compare메소드를 오버라이딩해 추가하면 2차원 배열도 정렬할 수 있다.

Arrays.sort(arr, new Comparator<int[]>() { //한번만 사용되기때문에 익명클래스(익명구현객체) 사용
	public int compare(int[] arr1, int[] arr2) { //2차원 배열을 2개씩 비교
		if (arr1[0] != arr2[0]) { // 두 2차원 배열의 x값 비교
			return arr1[0] - arr2[0]; // 오름차순 정렬(양수면 순서바꿈, 음수면 그대로둠). 앞 뒤 바꾸면 내림차순 정렬.
		} else {
			return arr1[1] - arr2[1]; //두 2차원배월의 y값 비교
		}
	}
});

 

익명클래스 사용법

 

문제

문제

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

입력

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

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

1 -1
1 1
2 2
3 3
3 4

 

내 답안

1. 모든 값 하나씩 비교(시간초과)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int arr[][];
		arr = new int[n][2];
		for (int i = 0; i < n; i++) {
			StringTokenizer token = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(token.nextToken());
			arr[i][1] = Integer.parseInt(token.nextToken());
		}
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				if (arr[i][0] > arr[j][0]) {
					int temp1 = arr[i][0];
					int temp2 = arr[i][1];
					arr[i][0] = arr[j][0];
					arr[i][1] = arr[j][1];
					arr[j][0] = temp1;
					arr[j][1] = temp2;
				} else if (arr[i][0] == arr[j][0]) {
					if (arr[i][1] > arr[j][1]) {
						int temp2 = arr[i][1];
						arr[i][1] = arr[j][1];
						arr[j][1] = temp2;
					}
				}
			}
		}
		for (int i = 0; i < n; i++) {
			bw.write(arr[i][0] + " " + arr[i][1] + "\n");
		}
		bw.flush();
	}
}

 

2. Comparator 인터페이스의 Compare메소드 오버라이딩

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int arr[][];
		arr = new int[n][2];
		for (int i = 0; i < n; i++) {
			StringTokenizer token = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(token.nextToken());
			arr[i][1] = Integer.parseInt(token.nextToken());
		}
		Arrays.sort(arr, new Comparator<int[]>() {
			public int compare(int[] arr1, int[] arr2) {
				if (arr1[0] != arr2[0]) {
					return arr1[0] - arr2[0];
				} else {
					return arr1[1] - arr2[1];
				}
			}
		});
		for (int i = 0; i < n; i++) {
			bw.write(arr[i][0] + " " + arr[i][1] + "\n");
		}
		bw.flush();
	}
}