[백준]10814_나이순 정렬_자바

코드

public class 백준10814_나이순정렬 {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<User> list = new ArrayList<>();

        int t = Integer.parseInt(bufferedReader.readLine());
        for (int i = 0; i < t; i++){
            String[] inputs = bufferedReader.readLine().split(" ");
            int age = Integer.parseInt(inputs[0]);
            String name = inputs[1];
            list.add(new User(age, name, i));
        }
        list.sort(User::compareTo);

        for (User user : list){
            user.print();
        }
    }

    static class User implements Comparable<User>{
        private int age;
        private String name;
        private int order;

        public User(int age, String name, int order) {
            this.age = age;
            this.name = name;
            this.order = order;
        }

        public void print(){
            System.out.println(age + " " + name);
        }

        @Override
        public int compareTo(User o) {
            if (age == o.age){
                return Integer.compare(order, o.order);
            }
            return Integer.compare(age, o.age);
        }
    }
}

 

풀이

주의할 점

처음엔 우선 순위 큐를 사용해서 문제를 풀었다.

문제에서 제시한 예제 입력은 정상적으로 뜨는 것처럼 보이나, 사실 나이가 같은 경우에 문제가 있다.

입력받은 순서대로 표시가 안뜨는 경우가 발생하는 점인데, 이는 우선 순위 큐의 특징 때문이다.

 

우선 순위 큐는 안정 정렬(Stable Sort)가 아니다.

 

안정 정렬이란?

정렬 전 동일한 키 값의 요소 순서가 정렬 후 유지가 되는 정렬 알고리즘

 

그렇기 때문에, 입력 순서가 명확히 안지켜질 수가 있다.

 

안정 정렬의 대표적인 주자로 버블 정렬, 삽입 정렬, 병합 정렬이 있다.

자바에선 Collections.sort, Arrays.sort(Object[])가 안정 정렬로 알고리즘으론 Tim Sort이라는 삽입과 병합 정렬을 섞은 알고리즘을 사용한다.

반대로 Arrays.sort(기본타입[])은 Dual-Pivot QuickSort 라는 알고리즘을 이용하여 비안정 정렬에 속한다.

 

풀이법

이를 반영하여 코드를 작성할 때 User 클래스를 만들고 Comparable 인터페이스를 구현한다.

Collections.sort를 할 때, Comparable 인터페이스 구현체를 넣어줘야하기 때문에 User::compareTo 메서드 참초를 해준다.

 

정상적으로 정렬이 된 것을 확인할 수 있다.