[Baekjoon] 11650 좌표 정렬하기

[Silver V] 좌표 정렬하기 - 11650

문제 링크

성능 요약

메모리: 74576 KB, 시간: 788 ms

분류

정렬(sorting)

문제 설명

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

입력

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

출력

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

---

알고리즘 과정

문제를 설명하기에 앞서…이 문제를 풀기에는 나는 너무 무력하고 아는 것이 없었다…

뭐 그냥 정렬하는 것인데 뭐가 어렵겠어 심지어 실버 5문제? 하고 덤볐던 나 자신이 너무 밉다.

모든 이해는 정말 많은 사이트에서 참고를 하고 도큐먼트도 많이 보고 단어 하나하나 찾아가면서 공부를 하여 이틀만에 조금 이해한 것 같지만 아직도 정확하게 이해는 하지 못하였다. 내가 이해한 내용이 맞는지도 모르겠다.

하지만 잊지 않게 미리 작성을 해두는 용이다.

차라리 누가 댓글로 “그거 틀렸어! 이렇게가 맞는거야!!!” 해준다면 정말 고마울 것 같다.

이 문제는 정말 참고를 많이 한 내용이므로 참고에 도움이 된 감사한 분들의 링크를 먼저 남긴다.

https://st-lab.tistory.com/110

https://st-lab.tistory.com/243

https://bada744.tistory.com/64

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=dg110&logNo=220418999915

Arrays.sort

public static <T> void sort(T[] a, Comparator<? super T> c) {
    if (c == null) {
        sort(a);
    } else {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, c);
        else
            TimSort.sort(a, 0, a.length, c, null, 0, 0);
    }
}

Sort 메소드를 보면 앞에 T[] a라고 된 것이 있다. 이것이 제네릭타입 객체배열이라고 한다.

그래서 제네릭이 뭔데?

제네릭이 뭔지 한 번 찾아보았는데 이해한 바로는 타입을 정해놓음으로써 다른 타입 체크와 형변환을 생략해버리는 것이다.

예를 들어, String 제네릭스는 String 객체만 사용가능, Integer이나 다른 것을 사용할 수 없음.

그리고 그 제네릭에는 어떤 타입이든 들어갈 수 있다는 것 같다.

결국에 보면 Sort 메소드에 배열로 타입을 정해놓은 것이다.

다음은 T[] a 옆에 있는 Comparator이 문제다.

Comparator이 뭔데?

Comparator는 일반 변수끼리나 숫자끼리 비교를 할 땐 부등호나 등호로 표시하면 되지만 객체를 비교할 땐 그렇게 할 수 없으니 사용하는 것이다.

Comparator는 인터페이스인데 인터페이스로 선언되면 무조건 구현을 해야한다.

구현해야 할 것은 Compare(T o1, T o2) 메소드다. 보면 알겠지만 두 개의 매개 변수로 들어오는 o1, o2 객체를 비교한다.

비교는 return o1 - o2 를 한다면 o1이 더 크다면 양수 같다면 0, 작다면 음수를 보내는 형식으로 될 것이다.

이러한 return 값으로 인하여 Arrays.sort에서 어떤 원소의 우선순위가 높은지 compare() 함수를 통해 알게 되고 정렬을 해주게 된다.

그리고 이 Comparator는 람다식으로 정의할 수 있다고 한다.

진짜 람다식은 또 뭐냐…

람다식은 익명함수라고도 한다.

식으로 함수를 사용하는 되게 간단하게 사용할 수 있는 방법이다.

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

정말 간단한 방법인 것 같다 이것을 이번에 사용하여 Comparator를 구현한다.

이제 문제는 내가 람다식이든 뭐든간에 이 문제의 Arrays.sort를 사용한 식이 아무리 봐도 이해가 안갔다는 것이다.

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

아니 분명 2차원 배열을 넣었는데…왜 일차원 배열끼리 뺄셈 덧셈을 하고 있지..?

내가 결국에 고민 고민하다가 생각한 내용은 sort 앞에 우리가 배열을 넣었기 때문에 타입이 배열 int[]로 되었다.

다음 e1, e2를 비교하는 과정이 난 잘 이해가 가지 않아서 이렇게 생각하기로 했다.

그래서 e1, e2에 들어가는 내용은

이차원 배열을 한 꺼풀 벗겨낸 일차원 배열이 각

[3, 4], [1, 1], [1, -1], [2, 2], [3, 3]

으로 들어간다고 생각했다.

이제 for문으로 생각하여 첫번째 배열과 두번째 배열 비교 이런 식으로 sort문이 자동으로 돌려준다고 생각했다.

틀린 생각이라면 다시 고쳐주실 분 찾습니당 ㅎㅅㅎ…

---

코드