Algorithms/백준

[백준] '좌표 정렬하기' - Java

LEFT 2023. 7. 18. 15:28

<문제 제시>

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


<문제이해>
1) 모든 원소들을 좌표별로 x를 오름차순 정렬하고, x가 같다면 y를 오름차순 정렬하라
2) 두 좌표를 모두 입력받았다고 가정해보자. 
그리고 arr[i][0] 와 arr[i+1][0] 을 정렬할 것이고 
만약 두 값이 같다면 arr[i][1] 과 arr[i+1][1] 을 비교할 것

>> 람다활용과 함께 Comparator를 오버라이딩하여 작성 

<예시 입출력>


<문제 해결 과정>

첫번째 정렬 기준은 x좌표의 오름차순이고,

x좌표가 같을 경우에는 y좌표의 오름차순 정렬을 해야한다.


Answer 1) 

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

StringTokenizer로 배열을 모두 입력받고, 정렬기준을 잘 정해야하는데,

먼저 람다식을 사용한 방법이다.

람다식은 예를 들어

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

이러한 코드가 있을때 이것을 요약하여

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

이렇게 쓸 수 있다.

따라서 위에 코드를 해석해보면

Arrays 클래스로 sort메서드를 사용하는데, e1, e2로 비교 객체를 정한다.

만약 이 객체들이 같을 경우에는 각 객체의 y좌표 부분 e1[1], e2[1] 을 뺀 값을 리턴한다.
>> return e1[1] - e2[1];

그렇지 않은 일반적 경우에는 e1[0] - e2[0] 처럼 x좌표를 비교하여 리턴한다.

람다식을 사용하지 않는 방법으로는

1) Comparator 클래스 사용

Arrays.sort(arr, new Comparator<int[]>() {
    @Override
    public int compare(int[] o1, int[] o2) {
        // 첫번째 원소가 같다면 (o1[0] == o2[0]
        // 두번째원소끼리 "비교" (return o1[1] - o2[1])
        if(o1[0] == o2[0]) return o1[1] - o2[1];

        else return o1[0] - o2[0];
    }
});

처럼 사용할 수 있다.

람다식은 위 Comparator 클래스 사용방법에서 "익명클래스를 생성할때 compare를 T[]타입을 가진 

매개변수 자체"를 람다식으로 바꿔쓴 것이다.


<전체코드>

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		
		int[][] arr = new int[N][2];
		
		// INPUT : 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());
		}
		
		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);
		
	}

}

Comparator 클래스 사용으로 객체 간 비교를 하는 방법과 람다식을 이용하여 객체 간 비교를 하는 방법을 모두 공부할 수 있었다. 람다식 표현이 간결하지만 이해가 되지 않을때는 Comparator클래스의 구조를 살펴보며 공부하는 것도 한 방법이 될 수 있을 것 같았다.


문제링크)
https://www.acmicpc.net/problem/11650

 

11650번: 좌표 정렬하기

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

www.acmicpc.net