[CLASS 2: 정렬] 백준 10814 나이순 정렬

10814번: 나이순 정렬

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

 

# 코드

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    int n = Integer.parseInt(br.readLine());

    TreeMap<Integer, ArrayList<String>> map = new TreeMap<>();
    StringTokenizer st;
    for (int i = 0; i < n; i++) {
      st = new StringTokenizer(br.readLine(), " ");
      int age = Integer.parseInt(st.nextToken());
      String name = st.nextToken();

      if (map.containsKey(age)) {
        // age 값에 해당하는 키가 이미 있으면 name을 value_list에 추가함
        map.get(age).add(name);
      } else {
        // 키가 없으면 value_list를 생성하고 map에 저장
        ArrayList<String> value_list = new ArrayList<>();
        value_list.add(name);

        map.put(age, value_list); // put
      }
    }

    Iterator<Integer> keys = map.keySet().iterator();
    while (keys.hasNext()) {
      int key = keys.next();
      for (int i = 0; i < map.get(key).size(); i++) {
        sb.append(key + " " + map.get(key).get(i)).append("\n");
      }
    }
    
    System.out.print(sb);
    br.close();
  }
}

• 먼저 TreeMap을 사용하여 key 값인 나이 순으로 자동 정렬되도록 한다. (시간이 더 걸리더라도 키 정렬하기 싫음 ㅠ)
• TreeMap의 value 값을 ArrayList<String>으로 하여 나이마다 줄줄이 리스트로 이름을 달아준다.
• map을 다루는 것이 익숙지 않아 어려움을 겪었던 문제였다.

 

 

 

그런데 다른 제출자분의 코드를 살펴보다 나이를 굳이 정렬하지 않아도 된다는 사실을 깨달았다. ⊙.☉

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // 나이별로 이름을 저장할 StringBuilder 배열 생성 (나이 범위: 0 ~ 200)
        StringBuilder[] p = new StringBuilder[201];

        // 각 나이에 해당하는 StringBuilder 초기화
        for (int i = 0; i < p.length; i++) {
            p[i] = new StringBuilder();
        }

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int age = Integer.parseInt(st.nextToken());
            String name = st.nextToken();

            // 해당 나이에 맞는 StringBuilder에 나이와 이름을 추가
            // age와 name을 '나이 이름' 형식으로 저장하고 줄바꿈 추가
            p[age].append(age).append(' ').append(name).append('\n');
        }

        // 최종 출력을 위한 StringBuilder
        StringBuilder sb = new StringBuilder();
        
        // 모든 나이의 StringBuilder 내용을 하나의 StringBuilder에 추가
        for(StringBuilder val : p){
            sb.append(val);
        }
        System.out.println(sb);
    }
}

• 나이 범위가 정해져 있어 배열을 마구 사용할 수 있다는 사실

 

역시 배열이 훨씬 빠르다