[백준] 11650번 - Comparator (java)

주어진 N개의 좌표를 x오름차순 정렬,
x가 같다면 y오름차순으로 정렬하는 문제이다.

처음엔 삽입정렬로 코드를 작성했으나 시간 초과가 걸렸다.

import java.util.*;
import java.io.*;

class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        int[] arrX = new int[N];
        int[] arrY = new int[N];
        
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine(), " ");
            arrX[i] = Integer.parseInt(st.nextToken());
            arrY[i] = Integer.parseInt(st.nextToken());
        }
        
        for(int i=1; i<N; i++){
            for(int j=i; j>0; j--){
            	if(arrX[j] < arrX[j-1] || (arrX[j] == arrX[j-1] && arrY[j] < arrY[j-1])){
                	int tmp = arrX[j-1];
                	arrX[j-1] = arrX[j];
                	arrX[j] = tmp;
                
                	tmp = arrY[j-1];
                	arrY[j-1] = arrY[j];
                	arrY[j] = tmp;
            	}else{
                	break;
            	}
            }
        }
        for(int i=0; i<N; i++){
            bw.write(arrX[i] + " " + arrY[i] + "\n");
        }
        br.close();
        bw.flush();
        bw.close();
    }
}

시간 초과

Buffered I/O를 사용했음에도 불구하고 좌표의 개수가 많은 경우 시간 초과가 일어난다.

즉 삽입 정렬 방법 말고 다른 방법을 사용해야 한다.

---

👉 Comparator

객체를 정렬하는 기준을 직접 정의할 때 사용하는 인터페이스

Comparator<T> comp = new Comparator<T>(){
	@Override
    public int compare(T a, T b){
    	...
        return 정수;
}

위가 Comparator의 기본적인 골자이며, compare이라는 추상 메소드를 사용한다. (T는 제네릭)

기본적으로는 정수(int)를 반환하는데, 반환하는 정수가 양수이냐, 0이냐, 음수이냐를 내 기준대로 정해 그걸로 순서를 판단한다.

예를들어 "음수를 반환하면 a가 b보다 앞에 와야한다" 라는 판단 기준을 내 마음속에서 정한다.
"0을 반환하면 두 객체의 순서가 같다."
"양수를 반환하면 a가 b보다 뒤에 와야한다" 등.

기본적으로는 "정렬"이 목적이다.

---

🙋‍♂️ 람다식

위 코드를 간단하게 사용하려면 다음과 같이 사용하면 된다.

Arrays.sort(arr, (a,b) -> Integer.compare(a, b));
// 오름차순 정렬

Arrays.sort(arr, (a,b) -> Integer.compare(b, a));
// 내림차순 정렬

아래는 예시이다.

Arrays.sort(persons, (p1, p2) -> p1.age - p2.age);
// 나이 오름차순. 반환값이 음수면 p1이 p2보다 앞에 와야한다.

Arrays.sort(persons, (p1, p2) -> p2.name.compareTo(p1.name));
// 이름 내림차순. compareTo는 String 클래스이다.
// 예를들어 p1이 "apple", p2이 "banana"이면
// "banana".compareTo("apple")은 양수이다.
// (apple이 banana보다 사전순 앞)
// 즉 "banana"가 앞에 오게 된다.

위 정보를 바탕으로 설계한 코드는 다음과 같다.

---

import java.util.*;
import java.io.*;

class Point{
	int x, y;
    Point(int x, int y){
    	this.x = x;
        this.y = y;
    }
}

class Main{
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        Point[] arr = new Point[N];
        
        for(int i=0; i<N; i++){
        	st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            arr[i] = new Point(x, y);
        }
        
        Arrays.sort(arr, (p1, p2) -> {
        	if(p1.x == p2.x){ return p1.y - p2.y; }
            return p1.x - p2.x;
        });
        
        for(Point p : arr){
        	bw.write(p.x + " " + p.y + "\n");
        }
        
        br.close();
        bw.flush();
        bw.close();
    }
}
        

맞았습니다!!