[BOJ - JAVA] 10814 - 나이순정렬(Comparator, Comparable 인터페이스)

# 주소

https://www.acmicpc.net/problem/10814

10814번: 나이순 정렬

# 문제

# 문제 해설 및 코드 리뷰

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        String[][] arr = new String[n][2];
        for(int i = 0; i < n; i++) {
        	arr[i][0] = scan.next();
        	arr[i][1] = scan.next();
        }
        Arrays.sort(arr, new Comparator<String[]>() {
        	public int compare(String[] s1, String[] s2) {
        		return Integer.parseInt(s1[0]) - Integer.parseInt(s2[0]);
        	}
        });
        for(int i = 0; i < n; i++) {
        	System.out.println(arr[i][0] + " " + arr[i][1]);
        }
    }
}

코드 길이만 보면 정말 간단한 문제일까 싶지만 이 문제는 정렬을 2차원으로 해석해야 하기 때문에 생각해야할 부분이 많습니다.

기본적으로 Arrays.sort를 쓰면 배열이 간단히 정리가 되는 것은 잘 알고 계실겁니다.

하지만 배열이 2차원이 되면 단순하게 라이브러리만으로 해결하기는 어렵기 때문에 Compare 인터페이스를 이용해야 합니다.

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

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

이 분이 Comparable과 Comparator에 대해 정말 상세히 정리를 해주셨습니다.

요약하자면 Comparable과 Comparator는 둘 다 인터페이스에 속합니다.

또한 Comparable 인터페이스에는 compareTo(T o) 메소드 하나가 선언할 수 있습니다.

이 말은 우리가 만약 Comparable을 사용하고자 한다면 compareTo 메소드를 재정의(Override/구현)을 해주어야 한다는 뜻입니다.

반면에 Comparator는 선언된 메소드가 많아서 헷갈릴 수 있겠지만, 우리가 실질적으로 구현해야 하는 것은 단 하나입니다.

바로 compare(T o1, T o2) 입니다.

 

원래 인터페이스(Inteface)란 함수의 껍데기만 있는 클래스라고 생각하시면 좋겠습니다.

예를 들어 자동차라는 것을 비교해서 생각해보자면 자동차는 바퀴가 4개 달려있고 전기, 휘발유로 작동하는 하나의 기계 장치로 우리는 이해하고 있습니다.

하지만 자동차마다 세분화되어 각각 차종마다 다른 설계도를 가지고 있는데, 이것을 우린 클래스라고 부릅니다.

그러므로 인터페이스란 여기서 '자동차'라는 추상적인 개념이 되는 것이고 클래스란 어떤 차종의 설계도를 의미합니다.

따라서 이 인터페이스를 이용하여 구현하기 위해서는 인터페이스에 선언된 메소드들(바퀴, 핸들 등)이 있을 것이고 이 인터페이스를 구현하는 클래스는 인터페이스에 선언된 메소드를 구체화하도록 강제가호 있습니다. 그리고 이것을 오버라이드(Override)라고 부릅니다. 

그렇기 때문에 인터페이스를 선언할 때에는 단순히 함수의 껍데기만 선언할 뿐 함수의 구체적인 내용은 작성하지 않습니다.

interface Airplain() {
	void plant();
    void wheel();
    }

이런식으로 함수의 껍데기만 정의하는 것을 인터페이스라고 부릅니다.

그렇다면 Comparable과 Comparater의 차이는 어떻게 구변할 수 있을까요?

이 인터페이스는 "객체를 비교할 수 있도록" 한다는 것에 의미를 품고 있습니다.

이 두 인터페이스는 비슷한 의미를 가지고 있지만 사용 방법은 전혀 다릅니다.

Comparable은 "자기 자신과 매게 변수를 비교" 할 때 사용되고

Comparater는 "두 매게변수를 서로 비교" 할 때 사용된다는 차이가 있습니다.

그리고 Comparable은 lang패키지에 있기 때문에 import를 안해주어도 되지만 Comparater는 util패키지에 속해있습니다.

그렇다면 쓰임새가 어떻게 다를까요?

class Student implements Comparable<Student> {
 
	int age;			
	int classNumber;	
	
	Student(int age, int classNumber) {
		this.age = age;
		this.classNumber = classNumber;
	}
	
	@Override
	public int compareTo(Student o) {
    	//비교내용 상세
	}
}

여기서 만약 나이를 기준으로 다른 요소들과 비교해야 한다면 어떻게 하면 될까요?

Comparable은 자기 자신과 비교를 한다고 말씀드렸습니다.

그렇기 때문에 자기 자신의 age와 매개변수 o의 age를 비교하면 되겠습니다.

만약 compareTo(Student o)의 상세 내용을 예로 들자면 이렇게도 작성할 수 있습니다.

if(this.age > o.age){
	return 1;
else
	return 0;
}

compareTo 메소드를 보면 int타입으로 선언했기 때문에 return도 int타입으로 반환해주어야 합니다.

그러므로 최종적인 코드는 이렇게 작성됩니다.

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
       Scanner scan = new Scanner(System.in);
       Student a = new Student(12,5);
       Student b = new Student(13, 6);
       int num = a.compareTo(b);
       if(num > 0)
    	   System.out.println("a가 더큼");
       else
    	   System.out.println("b가 더큼");
    }
}
class Student implements Comparable<Student> {
	   
	int age;			
	int classNumber;	
	
	Student(int age, int classNumber) {
		this.age = age;
		this.classNumber = classNumber;
	}
	
	@Override
	public int compareTo(Student o) {
    	if(this.age > o.age)
    		return 1;
    	else
    		return 0;
	}
}

당연히 출력하면 

b가 더큼

이런식으로 나오게 되는 것입니다.

이해가 가셨나요??

그럼 Comparater는 어떻게 사용할 수 있는지 알아보겠습니다.

Comparater는 아까 말했듯이 두 객체를 비교하는 것입니다.

기본적인 구조는

import java.util.Comparator;
public class ClassName implements Comparator<Type> { 
 
/*
  ...
  code
  ...
 */
 
	// 필수 구현 부분
	@Override
	public int compare(Type o1, Type o2) {
		//비교 상세
	}
}

이런 모양새를 가지고 있습니다.

그렇다면 Student 타입으로 계속해서 예시를 들어보겠습니다.

import java.util.*;
public class Main{
    public static void main(String[] args){
       Student a = new Student(11, 2);
       Student b = new Student(33, 3);
       Student c = new Student(14, 5);
       int g = a.compare(b, c);
       if(g > 0) {
    	   System.out.println("b가 c보다 큼");
       }else
    	   System.out.println("b가 c보다 작음");
	}
}
class Student implements Comparator<Student>{
	int age;
	int classNumber;
	Student(int age, int classNumber){
		this.age = age;
		this.classNumber = classNumber;
	}
	@Override
	public int compare(Student o1, Student o2) {
		return o1.age - o2.age;
	}
}

이렇게 만들 수 있을 겁니다.

하지만 계속해서 들어오는 입력값이 있다면 Student를 더 만들 수도 없는 노릇이기에 한계가 존재합니다.

그럼 이 현상을 어떻게 해결하면 좋을까요?

자 우리는 지금 정렬을 배웠습니다.

정렬은 기본적으로 오름차순을 기본 베이스로 깔고 시작합니다.

Comparater예제를 설명할 때 눈치를 채셨을지 모르겠지만 제일 밑에 return값을 o1.age - o2.age라고 했는데 눈치채셨나요??

자바에서는 return되는 값이 음수면 두 원소의 위치를 교환하지 않습니다. 즉, 기본적으로 오름차순이기 때문에 만약 o1.age - o2.age가 음수라면 당연히 o2가 더 크다는 것이고 o1, o2를 정렬했을 때 오름차순으로 연결되어 순서를 바꿀 필요가 없어지는 것입니다.

하지만 return되는 값이 양수가 되면 이야기가 달라집니다.

양수가 되면 o1.age - o2.age는 양수이고 o1 > o2이므로 두 원소의 위치는 바뀌게 됩니다.

따라서 정렬하면 {o2, o1} 이렇게 나오는 것입니다. 

 

그렇다면 다시 예제 문제로 돌아가서

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        String[][] arr = new String[n][2];
        for(int i = 0; i < n; i++) {
        	arr[i][0] = scan.next();
        	arr[i][1] = scan.next();
        }
        Arrays.sort(arr, new Comparator<String[]>() {
        	public int compare(String[] s1, String[] s2) {
        		return Integer.parseInt(s1[0]) - Integer.parseInt(s2[0]);
        	}
        });
        for(int i = 0; i < n; i++) {
        	System.out.println(arr[i][0] + " " + arr[i][1]);
        }
    }
}

Comparator를 활용하여 문제를 푼다면 어떻게 풀어야 할까요?

일단 arr에는 n행 2열의 2차원 크기의 배열을 선언합니다.

그리고 for문을 이용하여 arr의 1열과 2열에 각각 나이와 이름을 저장합니다.

 

그리고 이것을 정렬할건데, 아까 말했듯이 Arrays.sort를 이용하면 단순히 1차원의 크기일 때 가능하지만 2차원의 크기로 정렬하려면 조금 변형해야 한다고 말씀드렸습니다.

Arrays.sort(arr까지는 동일하나) new Comparator<String[]> 까지 입력해줄 것인데, 여기서 new Comparator는 String 타입으로(이름을 비교할 것이므로) 선언합니다.

public int compaare에는 (String[] 배열에서 가져오므로 s1, s2)를 각각 인자로 받되 return할 때에는 반드시 int타입으로 반환해야 합니다. 또한 이렇게 입력할 경우 나이순으로 오름차순에 맞게 정렬을 하게 되고 여기서 만약 나이가 같다면 입력순서대로 정렬이 됩니다.

꼭 기억하면 좋겠습니다.

compare메소드는 return이 양수이면 순서가 바뀌어서 정렬이 된다는 것을 말이죠.

감사합니다.