[Baekjoon] 10814번: 나이순 정렬

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

10814번: 나이순 정렬

문제 설명

N명에 대한 나이와 이름이 순서대로 주어진다. 주어진 정보들을 나이순으로 정렬하되 나이가 같다면 입력된 순서대로 출력하면 된다.

풀이 방법 1. Collections.sort() - 시간 초과

ArrayList에 age와 name이라는 필드를 가진 Member라는 클래스를 담고 Collections.sort()의 Comparator를 재정의해서 정렬하는 방식으로 해결하려 했지만 시간 초과가 발생하였다.

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

class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        List<Member> list = new ArrayList<>(N);
        
        for (int i = 0; i < N; i++) {
            String[] split = br.readLine().split(" ");
            list.add(new Member(Integer.parseInt(split[0]), split[1]));
        }
        
        Collections.sort(list, (m1, m2) -> {
            return m1.age != m2.age ? m1.age - m2.age : list.indexOf(m1) - list.indexOf(m2);
        });
        
        StringBuilder sb = new StringBuilder();
        for (Member m: list) {
            sb.append(m.age).append(" ").append(m.name).append("\n");
        }
        sb.delete(sb.length() - 1, sb.length());
        
        System.out.print(sb);
    }
    
    private static class Member {
        int age;
        String name;
        
        public Member(int age, String name) {
            this.age = age;
            this.name = name;
        }
    }
}

풀이 방법 2. TreeMap - 성공

TreeMap으로 자료구조를 변경하고 키에 age, 값에 ArrayList<String> 타입으로 같은 나이일 경우 이름을 순서대로 저장하도록 하였다. Java의 TreeMap은 Red-Black Tree로 구현되어 있어 시간 복잡도 O(log n)으로 문제를 해결 할 수 있다.

package baekjoon.sort;

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

public class BOJ10814 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        Map<Integer, ArrayList<String>> map = new TreeMap<>();

        for (int i = 0; i < N; i++) {
            String[] split = br.readLine().split(" ");
            Integer age = Integer.parseInt(split[0]);
            if (!map.containsKey(age)) {
                map.put(age, new ArrayList<>());
            }
            map.get(age).add(split[1]);
        }

        StringBuilder sb = new StringBuilder();
        for (Integer age : map.keySet()) {
            ArrayList<String> names = map.get(age);
            for (int i = 0; i < names.size(); i++) {
                sb.append(age).append(" ").append(names.get(i)).append("\n");
            }
        }
        sb.delete(sb.length() - 1, sb.length());

        System.out.print(sb);
    }
}