[백준 문제 풀이] 10814번 나이순 정렬

Junu Kim·2025년 12월 29일

Java baekjoon boj

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

74/89

[10814] 나이순 정렬

난이도: ★★☆☆☆ • solved on: 2025-12-29

문제 요약

문제 유형: 정렬 (Sorting), 안정 정렬 (Stable Sort)
요구사항: 회원을 나이 오름차순으로 정렬하되, 나이가 같으면 가입한 순 (입력 순) 을 유지해서 출력한다.

사용 개념

자료구조
- String[][] : 입력순 인덱스, "나이 이름" 원문을 한번에 저장
- Member[] : 나이/이름을 분리 저장 (커스텀 클래스)
알고리즘/기법
- 정렬 (Comparator)
- 안정 정렬 (stable sort) 활용
핵심 키워드
- 안정 정렬 (stable sort), 입력 순서 유지 (input order)

풀이 아이디어 및 코드

방법 1 : 배열을 활용한 인덱스 저장

문제 분해

각 입력에 대해 원래 순서를 arr[i][0]에 문자열로 저장한다.

Comparator에서 나이를 비교하고, 같으면 저장한 순서를 비교한다.
핵심 로직 흐름
arr[i] = (i, "age name")
정렬: age 오름차순, age 같으면 i 오름차순
arr[i][1] 출력
예외 처리

나이가 같은 경우 입력 순서 유지

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

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[][] arr = new String[n][2];
        for(int i = 0; i < n; i++){
            arr[i][0] = i + "";
            arr[i][1] = br.readLine();
        }
        Arrays.sort(arr, (a, b) -> {
            String[] person1 = a[1].split(" ");
            int person1Age = Integer.parseInt(person1[0]);

            String[] person2 = b[1].split(" ");
            int person2Age = Integer.parseInt(person2[0]);

            if(person1Age != person2Age){
                return person1Age - person2Age;
            }
            return Integer.parseInt(a[0]) - Integer.parseInt(b[0]);
        });

        StringBuilder sb = new StringBuilder();
        for(String[] data : arr){
            sb.append(data[1]).append("\n");
        }
        System.out.println(sb);
    }
}

방법 2 : 입력 파싱 1회 + 안정 정렬 활용

개선 포인트 (시간/공간)

방법 1은 정렬 비교할 때마다 split()과 parseInt()가 반복되어 비용이 크다.

입력 받을 때 나이/이름을 미리 분리 저장하면 비교가 매우 가벼워진다.

또한 이 문제는 “나이가 같으면 입력 순서 유지”인데, Java에서 객체 배열 정렬은 안정 정렬이므로 나이만 비교해도 입력 순서가 유지된다.
→ “순서 인덱스”를 따로 저장할 필요가 없어진다.
핵심 로직 흐름
members[i] = (age, name)
안정 정렬: age 오름차순만 비교
출력: age + " " + name
예외 처리

나이가 같을 때는 Comparator가 0을 반환 → 안정 정렬이라 입력 순서 유지

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

public class Main {

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

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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);
        }

        Arrays.sort(members, (a, b) -> a.age - b.age); // 나이만 비교 (안정 정렬 활용)

        StringBuilder sb = new StringBuilder();
        for (Member m : members) {
            sb.append(m.age).append(' ').append(m.name).append('\n');
        }
        System.out.print(sb);
    }
}

시간·공간 복잡도

방법 1

시간 복잡도: O(N log N * L)
- 비교 함수가 호출될 때마다 split() 등 문자열 처리 비용이 반복됨 (L = 문자열 길이)
공간 복잡도: O(N)

방법 2

시간 복잡도: O(N log N)
공간 복잡도: O(N)

어려웠던 점

입력 순서 정보를 어떻게 유지할지 설계하는 부분에서 난감했고, 처음에는 배열에 인덱스를 같이 저장하는 방식으로 해결했다.

배운 점 및 팁

이 문제의 핵심은 나이 같으면 입력 순서 유지인데, 안정 정렬(stable sort) 을 활용하면 인덱스 저장 자체가 필요 없어질 수 있다.
Comparator 안에서 split() 같은 문자열 파싱을 하면, 정렬 과정에서 같은 문자열을 계속 쪼개게 되어 비효율이 커진다. 따라서 파싱은 최초 저징시 진행하는 것이 좋다.