[백준알고리즘-JAVA]11650번 풀이(좌표 정렬하기) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 11650번 풀이입니다. 


* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 11650 (좌표 정렬하기)

문제

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

입력

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

출력

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

 

입력 예시

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

출력 예시

1 -1
1 1
2 2
3 3
3 4

성공 코드

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

public class Main {
	
	public static void main(String args[]) throws IOException{
	   	  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   	 
	   	 	int num = Integer.parseInt(br.readLine());
	   	 	
	   	 	int[][] arr = new int[num][2];
	   	 	
	   	 	for(int i =  0 ; i < num ; i++) {
	   	 		String[] str = br.readLine().split(" ");
	   	 		arr[i][0] = Integer.parseInt(str[0]);
	   	 		arr[i][1] = Integer.parseInt(str[1]);
	   	 	}
	   	 	
	   	 Arrays.sort(arr, (e1, e2) -> {
				if(e1[0] == e2[0]) {
					return e1[1] - e2[1];
				} else {
					return e1[0] - e2[0];
				}
			});
	   	 	
	   	for(int i = 0; i < num; i++) {
			System.out.println(arr[i][0] + " " + arr[i][1]);
		}
	   	 	
	   	 	
	   	 	}
		}

 좌표 정렬하기 알고리즘은 람다식 이용에 대해서 안다면 쉽게 해결할 수 있는 방법입니다. 여기서 람다식을 모르시는 분이 있을 수 있으니 차분히 STEP으로 알려드리겠습니다.

 

또한 좌표를 표현하기 위해서 2차원 배열을 생성해야 됩니다. 뭐 물론 Collection을 이용해서 구현할 수 돼있지만, 해당 방법이 가장 쉽게 풀이할 수 있기 때문이죠 ~

 

간단한 알고리즘 흐름도에 대해서 알려드리겠습니다.

---

알고리즘 플로우

입력받기 -> 받은 입력 2차원 배열에 넣어주기 -> 람다식을 이용하여 정렬하기 -> 출력하기

---

STEP1 받은 입력 2차원 배열에 넣어주기

해당 스탭은 굉장히 간단합니다. 입력을 받으면 즉시 선언한 2차원 배열에 차곡차곡 반복문을 통해 넣어주시면 끝!

for(int i =  0 ; i < num ; i++) {
	   	 		String[] str = br.readLine().split(" ");
	   	 		arr[i][0] = Integer.parseInt(str[0]);
	   	 		arr[i][1] = Integer.parseInt(str[1]);
	   	 	}

arr[0][0]	arr[0][1]
arr[1][0]	arr[1][1]
arr[2][0]	arr[2][1]
arr[3][0]	arr[3][1]
arr[4][0]	arr[4][1]

이런 식으로 하나씩 넣어주면 끝 ~!

---

STEP2 람다식 이해하기

람다식이란 자바에서 사용되는 하나의 기술로서 익명 함수를 지칭하는 용어입니다. 여기서 익명 함수란 일반적으로 우리가 함수를 정의할 때 함수의 이름을 작성하게 되죠

int c = sum(a, b);

public int sum(int a, int b){
	return a+b;
}

goakwlnvlk;an; eio wa;4 ASDFSDA 해당 식처럼 sum이라는 함수의 이름을 붙여줍니다. 여기서 해당 이름을 작성하지 않는 함수를 익명 함수라고 표현합니다~

 

이런 익명 함수를 쓰는 이유는 코드가 훨씬 간단해지며, 지연 연산을 수행하기 때문에 불필요한 연산을 최소화할 수 있습니다. 또한 멀티스레드를 활용하여 병렬 처리도 가능하지요

 

그러나 이러한 익명 함수는 호출이 까다롭고, 단순 for문 while문 사용보다는 성능이 떨어지고 자주 사용하면 가독성을 떨어뜨릴 수 있기 때문에 적절히 사용이 필요할 때만 사용하는 것을 권장합니다~

 

그렇다면 이러한 람다식을 어떻게 이용해야 할까요??

 

int c = (int a, int b) -> {return a+b;)

이런 식으로 아주 간단히 표현이 가능하게 되죠

 

그렇다면 이를 어떻게 문제에 적용해야 할지 생각해봐야 합니다. 

 

일반적으로 저희가 배열을 정렬할 때는 Arrays.sort() 함수를 이용합니다. 그러나 해당 식은 2차원 정렬을 지원하지 않기 때문에 람다식을 이용해야 하지요.

 

앞서 설명한 병렬 처리가 가능하기 때문입니다!!

Array.sort의 API를 살펴보면 인자로 2개의 인자를 받는 것을 알 수 있습니다.

 

public static <T> void sort(T[] a, Comparator<? super T> c)

여기서 <T>는 제네릭으로 데이터 타입 설정에 관한 것임으로 그냥 이해 못하셔도 상관없습니다. 즉, <>은 어떤 데이터 타입이 들어오든 해결해주는 기능으로 생각하시면 됩니다.

여기서 중요한 것은 바로 인자로 " 배열, 비교할 인자" 이 2개를 인자로 넣는 것입니다.

 

 Arrays.sort(arr, (e1, e2))

이런 식으로 정렬을 하면 되죠. 그러나 저희는 문제에서 X좌표가 우선 정렬되고 만약 같을 경우 Y를 비교를 해야 합니다. 그렇기 때문에 저희는 람다식, 즉, 익명 함수를 통해서 함수를 재정의 해줘야 할 필요성이 있습니다.

Arrays.sort(arr, (e1, e2) -> {
				if(e1[0] == e2[0]) {
					return e1[1] - e2[1];
				} else {
					return e1[0] - e2[0];
				}
			});

바로 요렇게 말이죠. 만약 X좌표가 같다면 Y좌표를 비교하고 그게 아니면 그냥 바로 반환을 해주는 Comparator 비교 방법이죠.

 

여기서 왜 반환을 저렇게 하나요? 의문이 드실 수 있습니다.

 

그러나 Comparator 비교 방식은 반환 값이 양수냐, 음수냐를 통해서 정렬을 해주는 방식입니다. 즉 e1 [1] - e2 [1] 이 수가 양수가 된다면 e1이 더 큰 수가 될 것이고, 그 반대면 e2가 더 큰 수가 됩니다.

 

이런 식으로 반환을 해주면, Array.sort를 통해서 배열을 자동으로 정렬을 해주게 되죠.

 

더 자세한 Comparator에 관한 내용은 이후 새롭게 다뤄보도록 하겠습니다.

---

 

해당 알고리즘을 통해 람다식, Comparator에 대해서 간략히 알아보았는데 더욱 심화된 내용을 곧 글로 작성해 드리겠습니다~

 

생각보다 람다식, Comparator에 관한 내용은 자주 등장함으로 익혀두심을 추천합니다 ~