백준 10814번: 나이순 정렬

N명의 온라인 저지 회원의 정보를 나이순으로, 나이가 같으면 가입한 순서대로 정렬하는 문제입니다. 이 문제의 핵심은 '안정 정렬(Stable Sort)'의 개념을 이해하고, Java의 내장 정렬 기능이 이를 지원한다는 사실을 활용하는 것입니다.

---

✅ 문제 개요

항목	내용
문제 번호	10814번 - 나이순 정렬
난이도	실버 5
핵심 알고리즘	정렬, 안정 정렬(Stable Sort)

---

✅ 문제 설명 요약

• 입력:
  1. 첫째 줄: 회원의 수 N (1 ≤ N ≤ 100,000)
  2. 이후 N개의 줄: 각 회원의 나이와 이름이 공백으로 구분되어 주어짐
• 출력: 정렬된 회원 정보를 나이 이름 형식으로 한 줄에 하나씩 출력
• 정렬 규칙:
  1. (1차 기준) 나이가 증가하는 순서로 정렬한다.
  2. (2차 기준) 나이가 같으면, 가입한 순서(입력 순서)대로 정렬한다.

---

✅ 풀이 전략

이 문제는 '나이'라는 1차 기준과 '가입 순서'라는 2차 기준을 가진 다중 조건 정렬 문제입니다. 특히 '가입 순서'라는 조건은 이 문제가 안정 정렬(Stable Sort)을 요구한다는 중요한 단서입니다.

1️⃣ 핵심 과제: 안정 정렬 (Stable Sort)

• 안정 정렬이란?: 정렬할 키(key) 값이 동일한 원소들의 상대적인 순서가 정렬 후에도 그대로 유지되는 정렬 방식을 말합니다.
• 이 문제에서 '나이'가 바로 정렬 키 값입니다. '나이가 같으면 가입한 순서대로'라는 말은, 나이가 같은 회원들끼리는 원래 입력받은 순서를 바꾸지 말라는 의미이므로, 안정 정렬을 사용해야 합니다.

2️⃣ Java의 정렬 알고리즘 활용

• 매우 중요한 사실: Java의 Arrays.sort(Object[])나 Collections.sort()는 안정 정렬(Stable Sort)을 보장하는 Timsort 알고리즘을 사용합니다.
• 이것이 의미하는 바는, 우리가 정렬 기준을 '나이' 하나만 알려줘도, 나이가 같은 회원들은 Java가 알아서 원래 순서를 유지시켜 준다는 것입니다.
• 따라서 우리는 2차 기준인 '가입 순서'를 직접 코드로 구현할 필요가 없습니다.

3️⃣ 데이터 구조 및 Comparator 구현

1. Member 클래스 만들기: 회원의 나이(int age)와 이름(String name)을 함께 관리하기 위해 별도의 Member 클래스를 정의하는 것이 좋습니다.
2. Comparator 구현: Arrays.sort()에 정렬 기준을 알려주기 위해 Comparator를 사용합니다. 람다식을 이용하면 간결하게 구현할 수 있습니다.
3. 정렬 로직: 안정 정렬의 특성을 활용하므로, 우리는 1차 기준인 '나이'만 비교하면 됩니다. 나이가 같은 경우, Comparator가 0을 반환하게 하면 Arrays.sort가 자동으로 기존 순서를 보장해 줍니다.

// Comparator를 람다식으로 구현
Arrays.sort(members, (m1, m2) -> {
    // 나이만 비교하여 오름차순 정렬
    // m1.age와 m2.age가 같으면 0이 반환되고,
    // 안정 정렬 특성에 의해 원래 순서가 유지된다.
    return m1.age - m2.age;
});

4️⃣ 알고리즘 설계

1. age와 name을 저장할 Member 클래스를 정의합니다.
2. N개의 Member 객체를 저장할 배열을 생성합니다.
3. N명의 회원 정보를 입력받아 Member 객체를 생성하고 배열에 저장합니다.
4. Arrays.sort() 메소드에 위에서 설계한 '나이만 비교하는' Comparator 로직을 전달하여 배열을 정렬합니다.
5. 정렬된 배열을 순회하며 각 회원의 정보를 형식에 맞게 출력합니다.

---

✅ Java 코드 예제

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.Comparator;

// 회원 정보를 저장할 Member 클래스
class Member {
    int age;
    String name;

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

public 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));

        int N = Integer.parseInt(br.readLine());

        Member[] members = new Member[N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int age = Integer.parseInt(st.nextToken());
            String name = st.nextToken();
            members[i] = new Member(age, name);
        }

        // Comparator를 사용하여 나이순으로 정렬
        Arrays.sort(members, new Comparator<Member>() {
            @Override
            public int compare(Member m1, Member m2) {
                // 나이만 비교하여 오름차순 정렬
                return m1.age - m2.age;
            }
        });

        // 정렬된 결과 출력
        for (int i = 0; i < N; i++) {
            bw.write(members[i].age + " " + members[i].name + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

---

⚠️ 실전 주의사항

항목	설명
안정 정렬(Stable Sort)의 중요성	Java의 Arrays.sort(Object[])가 안정 정렬이라는 사실을 알고 있다면, 2차 기준(가입 순서)을 구현하는 수고를 덜 수 있습니다. 이는 코딩 테스트에서 매우 중요한 지식입니다.
객체 배열 정렬	int[] 같은 기본 타입 배열의 Arrays.sort()는 퀵 정렬 기반이라 안정 정렬이 아니지만, Object[] 즉, 객체 배열의 Arrays.sort()는 Timsort 기반이라 안정 정렬입니다.
데이터 클래스	나이, 이름처럼 연관된 데이터는 별도의 클래스로 묶어 관리하는 것이 객체 지향의 좋은 습관이며, 코드의 가독성과 유지보수성을 높여줍니다.
입력 성능	N이 최대 100,000이므로, Scanner보다는 BufferedReader를 사용하는 것이 시간 초과를 피하는 데 안전합니다.

---

📝 마무리 요약

✔️ '가입한 순서', '원래 순서'와 같은 정렬 조건은 안정 정렬(Stable Sort)을 요구하는 강력한 힌트입니다.
✔️ 다행히 Java의 Arrays.sort() (객체 대상)는 안정 정렬을 기본적으로 지원합니다.
✔️ 따라서 우리는 1차 기준인 '나이'에 대해서만 정렬 로직을 Comparator로 구현하면 됩니다.
✔️ 나이가 같은 회원들은 Arrays.sort()가 알아서 원래 입력받은 순서를 그대로 유지시켜 줍니다.