백준 알고리즘 문제(83) - 좌표 정렬하기

x와 y의 좌표를 입력받아서 순서대로 출력하는 문제다.
x좌표를 오름차순으로 정렬하되, x값이 같다면 y의 값을 기준으로 정렬해야한다.

나는 2차원 배열을 만들어 행마다 x, y값을 입력받을 것이다.
행에 해당하는 1열을 기준으로 비교해서 정렬하고, 순차적으로 비교해서 값이 같다면, 2열의 값을 비교해 바꿔줄 것이다.

카운팅정렬은 200,000만큼의 공간을 차지하므로 사용하지 않겠다.

버블정렬을 이용한 방법이다. 효율이 O(N^2)이므로 효율이 상당히 떨어진다고 생각했는데 아니나다를까 답은 나오지만 반복문을 너무 많이 사용해서 맞는 답에 시간초과가 떳다.

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


public class java_io {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args) throws IOException {
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st;
		int[][] arr = new int[N][2];
		//2차원 배열에 x y 값을 입력
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine()," ");
			arr[i][0]= Integer.parseInt(st.nextToken());
			arr[i][1] =Integer.parseInt(st.nextToken());
		}
		int temp = 0;
		for(int i=1; i<N; i++) {
			for(int j=0; j<N-i; j++) {
				if(arr[j][0]>arr[j+1][0]) {
					chg(arr, j, j+1);
				
				}
			}
		}
        //x값이 같을 경우에 y값을 비교하는 메소드
		for(int i =0; i<N-1; i++) {
			int temp_y = 0;
			if(arr[i][0] == arr[i+1][0] && arr[i][1] >arr[i+1][1]) {
				temp_y = arr[i][0];
				arr[i][0] = arr[i+1][0];
				arr[i+1][0] = temp_y;
				
				temp_y = arr[i][1];
				arr[i][1] = arr[i+1][1];
				arr[i+1][1] = temp_y;
			}
			
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<N; i++) {
			sb.append(arr[i][0] +" " + arr[i][1]).append('\n');
		}
		
		System.out.print(sb);
		
	}
	//x값을 비교해서 y값도 함께 바꿔주는 메소드
	public static void chg(int[][] arr_chg, int i, int j) {
		int temp = arr_chg[i][0];
		arr_chg[i][0] = arr_chg[j][0];
		arr_chg[j][0] = temp;
		
		temp = arr_chg[i][1];
		arr_chg[i][1] = arr_chg[j][1];
		arr_chg[j][1] = temp;
		
	}
	// y값을 대소 비교해주는 메소드
	public static void chg_y(int[][] arr_chg, int i, int j) {
		int temp = arr_chg[i][0];
		arr_chg[i][0] = arr_chg[j][0];
		arr_chg[j][0] = temp;
		
		temp = arr_chg[i][1];
		arr_chg[i][1] = arr_chg[j][1];
		arr_chg[j][1] = temp;
		
	}
}

자주 즐겨보는 Stranger's lab에서는 람다식을 사용했다. 나는 람다를 다룰줄 모르므로 이번 기회에 배워보겠다.

람다는 간편한 함수다.

생성자에서는 따로 지정해줘야하는 것들을 람다로 간편하게 표현할 수 있다.
예를 들면,
public int sum(int a, intb){
return a+b;
}
를 아래와 같이 표현한다.
(int a, int b) -> {return a+b;})

이번 경우엔 Arrays.sort를 람다식으로 구현해야한다. Comparator을 Overide해서 사용한다.
e1은 선행원소, e2는 후행원소이며, e1이 e2보다 작으면 -1을 반환하고 같다면 0, 크다면 1을 반환한다.
if(e1[0] < e2[0]) {
return -1;
}
else if(e1[0] == e2[0]) {
return 0;
}
else {
return 1;
}
결과적으로, return e1[0] - e2[0]로 표현 가능하다.

5
3 4
1 1
1 -1
2 2
3 3
에서 3 4 는 e2로 취급되고, 1 1은 e1으로 취급되어 계산된다. 이건 Comparator 자체에서 Arrays.sort안에서 연산할 때, 구현하는 방식으로 Timsort를 이용하므로 이렇게 계산된다고한다.

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


public class java_io {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args) throws IOException {
		int N = Integer.parseInt(br.readLine());
		
		int[][] arr = new int[N][2];
		
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][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];
			}
		});
		
		StringBuilder sb = new StringBuilder();
		for(int i =0; i<N; i++) {
			sb.append(arr[i][0] +" " +arr[i][1]).append('\n');
		}
		System.out.println(sb);
	}
}

출처 : Stranger's lab
내가 알아야할 부분은 결국

생성자를 람다식으로 간결하게 표현이 가능하다.

2차원 배열은 Comparator을 1차원 대입하면, 사용가능하다. 결국 람다식을 Arrays.sort에서 이용하는 방법을 알아야한다.