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

문제

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

출력

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

예제입력

3
21 Junkyu
21 Dohyun
20 Sunyoung

예제출력

20 Sunyoung
21 Junkyu
21 Dohyun

문제풀이 - Compareable에 정의된 compareTo(비교객체) 함수를 구현하면 된다.

compareTo(Object o)을 구현
-- 나이 순(Integer)으로 정렬

Integer.compare(int x, int y)

Integer.compare(x, y);

1) x > y : 양수 리턴
2) x < y : 음수 리턴
3) x = y : 0 리턴

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main10814 {

    /**
     * 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다.
     *  이때, 회원들을 나이가 증가하는 순으로,
     *  나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.
     */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());

        List<Member> members = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            members.add(new Member(Integer.parseInt(st.nextToken()), st.nextToken()));
        }

        //Dual-Pivot QuickSort
        Collections.sort(members);

        for (Member member : members) {
            System.out.println(member.getAge() + " " + member.getName());
        }
    }

    static class Member implements Comparable<Member>{
        private final int age;
        private final String name;

        public Member(int age, String name){
            this.age = age;
            this.name = name;
        }
        public int getAge() {
            return age;
        }

        public String getName() {
            return name;
        }

        @Override
        public int compareTo(Member member) {
            // (현재 객체, 비교 객체)
            /**
             * (현재 > 비교) 양수
             * (현재 < 비교) 음수
             * (현재 == 비교) 0
             */
            return Integer.compare(this.age, member.age);
        }
    }
}

Java의 Collections.sort() 메서드와 Arrays.sort() 메서드는 내부적으로 어떤 정렬알고리즘을 사용할까?

Dual-Pivot Quicksort 알고리즘

Quicksort()의 변형으로 Java7 부터 사용되기 시작했다.
평균적으로 O(nlogn)의 시간복잡도를 가진다.

특징

1) 두 개의 피벗을 사용하여 배열을 세 부분으로 나눈다.
-- 첫 번째 부분은 첫 번째 피벗보다 작은 요소들로 구성
-- 두 번째 부분은 두 피벗 사이에 위치한 요소들로 구성
-- 세 번째 부분은 두 번째 피벗보다 큰 요소들로 구성

2) 시간복잡도 : 평균적으로 O(nlogn)의 시간복잡도를 가지며 최악의 경우 O(n^2)이 될 수 있다. (대부분의 상황에서는 성능이 매우 뛰어나다.)
3) 메모리 효율성 : in-place 알고리즘이기 때문에 추가적인 메모리 사용이 거의 없으며, 메모리 사용을 최소화하는데 유리하다.

Java에서는 작은 배열에 대해서는 Insertion Sort(삽입정렬)을 사용하여 성능을 최적화한다. Quicksort의 최악의 경우를 방지하기 위해 Hybrid Sorting 방식을 사용하여 Insert Sort와 결합하기도 한다.

Arrays.Sort()의 경우

Java에서 int, double 등 원시 타입 배열을 정렬할 때에는 Timsort 알고리즘을 사용한다.
Timsort는 Merge Sort와 Insertion Sort를 조합한 알고리즘으로, 이미 정렬된 경우 성능이 좋다.