[Java] 백준 10814번:나이순 정렬

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

10814번: 나이순 정렬

 

[코드1] 

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

/*
3
21 Junkyu
21 Dohyun
20 Sunyoung*/

public class Main10814 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n= Integer.parseInt(br.readLine());
        StringTokenizer st;
        ArrayList<Person> personArrayList= new ArrayList<>();

        //사람 정보를 리스트에 넣기
        for (int i = 0 ; i<n;i++){
            st = new StringTokenizer(br.readLine()," ");

            int age = Integer.parseInt(st.nextToken());
            String name = st.nextToken();
            Person person = new Person(age,name);

            personArrayList.add(person);

        }
        //정렬
        Collections.sort(personArrayList,new Comparator<Person>(){
            @Override
            public int compare(Person p1, Person p2) {

                return p1.age - p2.age;
            }

        });


        for(int i =0;i<n;i++){
            System.out.println(personArrayList.get(i).getAge()+" "+personArrayList.get(i).getName());
        }



    }


    static class Person {

        int age;
        String name;

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

        public int getAge (){
            return age;
        }

        public  String getName () {
            return name;
        }


    }
}

코드 1같이 풀었을 경우는 최악의 경우 시간 복잡도가 O(n^2) 이 나오는 거같다. (약 1600ms) 

[코드 2] -수정

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


/*
3
21 Junkyu
21 Dohyun
20 Sunyoung*/

public class Main10814 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;

        //나이와 같은 인덱스 번호에 정보를 저장하려고 한다.
        StringBuilder[] ageArray = new StringBuilder[201];

        for (int i = 0; i < ageArray.length; i++) {
            ageArray[i] = new StringBuilder();
        }

        for (int i = 0; i <n; i++){
            String str = br.readLine(); // 입력 값을 저장해둔다.
            int age = Integer.parseInt(new StringTokenizer(str).nextToken());// 나이 값만 따로 저장해둔다.

            //ageArray에 age와 같은 인덱스 번호에 str을 저장한다.
            ageArray[age].append(str).append("\n");
        }

        //출력한다.
        StringBuilder sb = new StringBuilder();
        for (StringBuilder s : ageArray) {
            sb.append(s);
        }

        System.out.println(sb);

    }



}

(약 400ms)

 

코드 2처럼 풀땐 훨씬 시간을 단축 시킬 수 있다.

 

1) StringBuilder(ageArray)최대나이크기+1 만큼의 크기로 배열을 만들어준다.

2) ageArray[나이] 에 "나이 이름"을 append한다.

3) 다 넣었다면 sb에 반복문을 통하여 ageArray에 들어 있는 모든 값들을 차례대로 넣어 출력시킨다.