[백준] 11650번 : 좌표 정렬하기 - JAVA [자바]

www.acmicpc.net/problem/11650

11650번: 좌표 정렬하기

 

---

• 문제

 

 

 

 

이번 문제는 람다식(lambda)만 쓸 줄 알면 그리 어렵지 않게 풀 수 있다. (오랜만입니다..)

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

보통 문제를 보면 가장 먼저 생각하는 것이, 아! 2차원 배열을 사용해야겠다! 일 것이다. 아쉽게도 Arrays.sort() 자체는 2차원 배열의 정렬을 할 수가 없다. 그렇기 때문에 람다식을 사용하여 Arrays.sort() 확장할 수 있어야한다.

 

앗.. 전 람다식을 쓸 줄 모르는데요..?!

 

걱정하지 않아도 된다. 이번 문제에서는 그렇게 어렵게 쓰이진 않는다. 일단 람다식은 가장 쉽게 말하자면 '함수'라는 것 정도만 알아도 된다.

사용 방법은 다음과 같다.

(매개변수1,...) -> {함수;}

 

감이 안온다면 다음을 보면 된다.

// 람다식 X
public int sum(int a, int b) {
	return a + b;
}

// 람다식 O
(int a, int b) -> {return a + b;}

 

엄청 간편하지 않은가? 위와같이 함수의 이름 없이 람다식으로 구현한 함수를 일명 익명함수라고 하기도 한다. 만약 어떤 변수에 a 와 b의 합을 구하고 싶다면 다음과 같이 하면 된다.

 

// 람다식 X
int c = sum(a, b);
public int sum(int a, int b) {
	return a + b;
}

// 람다식 O
int c = (int a, int b) -> {return a + b;}

 

이렇게 람다식을 쓰지 않을 때보다 훨씬 코드가 간결해지는 장점이 있다. 특히 일회성으로 함수를 써야할 경우 굳이 메소드를 하나 작성하기보다는 람다식으로 구현하는 것이 개발자의 의도라던가 가독성 등에서 훨씬 좋아지는 장점이 있다. (물론 과하면 가독성을 떨어뜨리니 뭐든 적당히 쓰자..)

 

 

그렇다면 Arrays.sort() 에는 람다식을 어떻게 써야할까?

먼저, 자바 API 를 보면 다음과 같이 설명한다.

 

 

일단 sort 메소드는 두 가지 인자를 받을 수 있다.

첫 번째는 제너릭타입 객체배열(T[]). 뭔 말인가 싶을 수도 있겠다만, 일단은 클래스, 오브젝트, 자료형 등 어떠한 타입이든 상관없이 배열의 형태로 받을 수 있다는 의미다. 만약 int[] 형 배열을 쓸 경우 T 는 int 로 결정되며, boolean[] 배열일 경우 T는 boolean 으로, 만약 Student 라는 클래스 객체를 배열로 만들어 Student[] 형태의 객체배열로 만든 뒤, sort() 에 넣을경우 T 는 Student 가 된다는 의미다.

 

즉, 우리는 2차원 배열을 받을 것이니 int[][] 가 될 것이다. 이 의미는 다른의미로 int[] 가 하나의 타입이고, int[] 타입의 배열형태인 int[][] 라는 1차원 배열이라고 볼 수도 있겠다. (의미상 그렇다는 것.. 이해하기 쉬우라고 풀어서 설명했다.) 즉, T = int[] 가 될 것이다.

 

 

그리고 가장 중요한 Comparator<? super T> c 이다. 일단 간단하게 설명만 하자면, <? super T> 는 상속관계에 있는 타입만 자료형으로 받겠다는 의미다. 즉, T 타입이 자식클래스가 되고, T의 상속관계에 있는 타입까지만 허용하겠다는 의미다. 이 문제에서는 상속관계에 있는 데이터를 정렬하지 않기 때문에 이를 생략하여 <T> 이렇게 봐도 된다.

 

무엇보다 중요한 것은 Comparator 의 경우 람다식으로 표현 할 수 있다는 것이다. Comparator 까지 설명하긴 너무 기니.. 일단 간단하게 말하자면 우선순위를 사용자화 한다고 보면 되고, compare 메소드를 오버라이딩하여 compare 메소드 안에 자신만의 비교 방법(우선순위 판단)을 구현하면 된다.

 

자세한 Comparator 내용은 아래 글을 통해 확인하시길 바란다.

 

st-lab.tistory.com/243

자바 [JAVA] - Comparable 과 Comparator의 이해

 

그럼 한 번 적용해보자. arr[N][2] 배열이 있고, 두 좌표를 모두 입력받았다고 가정해보자. 그리고 arr[i][0] 와 arr[i+1][0] 을 정렬할 것이고 만약 두 값이 같다면 arr[i][1] 과 arr[i+1][1] 을 비교할 것이다.

 

위 말대로라면 T 는 int[] 가 될 것이고, arr[] 의 [1] (arr[i][1])을 비교하기 위해 사용자화해야한다.

 

즉, 아래와 같을 것이다.

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

 

 

 

물론 이렇게 써서 해도 된다!

다만 좀 더 쉽게 쓰고자 람다식을 써도 된다는 것을 보여주고자 하는게 바로 포인트다. 아까 말했듯이 람다식은 따로 메소드를 구현하지 않고 함수로 바로 쓸 수 있다고 했다. 즉, 더욱 간편하게 쓸 수도 있다. 위 코드에서 Comparator 안에 볼 수 있는 메소드라 하면 compare 이다. 이 또한 람다식으로 변경하면 다음과 같이 짤 수 있다.

 

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

 

 

즉, Comparator에 대해 익명 클래스를 생성할 때 compare을 T[] 타입을 가진 매개변수를 람다식으로 바꾸어 쓸 수 있다는 것이다.

 

 

 

 

 

 

 

---

• 3가지 방법을 이용하여 풀이한다.

 

 

위에서 설명한 Arrays.sort 을 확장한 정렬 방법을 사용하여 풀 것이다.

입력과 출력만 달리하여 보여줄 것인데, 입력은 Scanner 와 BufferedReader 을 통한 방법으로 보여줄 것이고, 출력은 System.out.println() 을 반복하여 출력하는 방법과 StringBuilder 를 통한 출력방법을 보여줄 것이다. 다만 System.out.println() 은 Scanner 에서만 쓸 것이다.

 

즉 아래와 같이 3가지 방법을 보여줄 것이다.

1. Scanner + System.out.println()
2. Scanner + StringBuilder
3. BufferedReader + StringBuilder

 

 

---

• 풀이

- 방법 1  :  [Scanner + System.out.println()]

 

import java.util.Scanner;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		int[][] arr = new int[N][2];
		
		for(int i = 0; i < N; i++) {
			arr[i][0] = in.nextInt();
			arr[i][1] = in.nextInt();
		}
		
		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 < N; i++) {
			System.out.println(arr[i][0] + " " + arr[i][1]);
		}
	}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

람다식에 대해서는 최대한 이해하기 쉽도록 설명하려고 노력했으나.. 만약 어렵다면 Comparator 방법을 써도 된다!

---

- 방법 2  :  [Scanner + StringBuilder]

 

 

출력 부분만 바꿔주는 방법이다. 이 방법만 바뀌어도 꽤 많은 시간을 줄일 수 있다.

 

import java.util.Scanner;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		int[][] arr = new int[N][2];
		
		for(int i = 0; i < N; i++) {
			arr[i][0] = in.nextInt();
			arr[i][1] = in.nextInt();
		}
		
		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);
	}
}

 

 

 

 

---

- 방법 3  :  [BufferedReader + StringBuilder] 

 

 

 

 

이번에는 입력을 바꿔서 사용해보는 방법이다. 참고로 문자열 분리는 StringTokenizer 을 사용할 것이다.

 

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

public class Main {
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		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);
	}


}

 

 

먼저 입력 개수 N 을 받는다.

다음 줄에 StringTokenizer 을 생성과 동시에 BufferedReader.readLine() 으로 한 줄을 입력받으면서 공백(" ")으로 구분시켜준다.

 

다음으로 맨 처음 max 값을 -1 로 초기화 한다. (입력받을 값이 0보다 크거나 같기 때문)

 

그리고 StringTokenizer 의 토큰(분리된 문자열)을 꺼내오면서 value에 저장한 뒤 max 값과 비교하고, sum 에 value 값을 더해준다.

 

그리고 굳이 매번 하나의 value 마다 (value/max)*100 을 해주면서 sum 에 더해주는 것 보다는 마지막에 한번에 연산한 값을 출력해주는게 연산을 덜 할 것이다. (이때 sum 이 double이라 연산값 또한 double 로 형변환 되어 반환된다.)

 

예로들어 3, 7, 6, 2 라는 값을 입력받았을때

(3/7)*100 + (7/7)*100 + (6/7)*100 + (2/7)*100 이렇게 하나

((3+7+6+2) / 7)*100 을 하나 값은 같기 때문에 상관이 없다.

 

 

 

 

※ 참고로 오차범위가 10^(-2) 이니까 자동형변환을 사용해도 된다는 것이다. 만약 오차범위가 아주아주 작아야 한다면(예로들어 1/1,000,000,000,000) 모두 double형으로 해주는게 가장 안전하다. 왜냐하면 형 변환을 하는 과정중에 데이터 손실이 발생할 수도 있기 때문이다.

 

 

 

 

 

 

 

 

---

• 성능

 

위에서 부터 순서대로

 

채점 번호 : 20294638  -  방법 3 : BufferedReader + StringBuilder

채점 번호 : 20294632  -  방법 2 : Scanner + StringBuilder

채점 번호 : 20294627  -  방법 1 : Scanner + System.out.println()

 

 

너무 당연한 말이겠지만 BufferedReader 의 성능이 훨씬 좋다..

---

• 정리

 

(오랜만에 포스팅하는 것 같다. 근래 하나 개발하고 있는 것이 있어 거기에 몰두하다 보니...)

 

이번 문제는 그리 어려운 문제는 아니지만 아마 람다식이라던가 Comparator 사용법을 알고있지 못하면 조금 어렵게 느껴질 수도 있다. 그러나 백준 문제가 아니라 앞으로 자바를 사용한다면 위 두가지는 반드시 알아두어야 한다. (물론 람다식에 대해서는 조금 논쟁의 여지가 있긴 하지만 람다식이 갖고있는 확실한 장점이 몇 가지 있다보니 알아두는 것이 100배는 좋다)

 

만약 이해가 잘 안되는 부분이 있다면 댓글 남겨주시면 최대한 빠르게 (늦어도 하루) 답변드리도록 하겠다.