[백준] 나이순 정렬 in Java

📍 문제

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

📍 코드 설명

나이 순으로 정렬하고 나이가 같다면 먼저 입력된 순으로 정렬하는 문제이다.

 

두가지 방법으로 풀어볼수있다.

1. class 를 이용하여 age, name을 입력받고 compareTo를 override하여 age순으로 정렬한다

2. 배열 index로 age를 사용하여 나이와 이름을 저장한다.

📍 코드

✔️ class - compareTo 코드

1. class로 Person을 만들어 age와 name을 변수로 가진다

 

2. Comparable의 compareTo를 구현한다.

이때, 나이를 기준으로 정렬한다

추후 출력에 용이하기 위해 출력 형식에 맞춰 ToString도 구현한다.

 

3. List<Person>으로 입력받고, Collection.sort()하여 나이순으로 정렬한 뒤 출력한다.

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

class Main {
    static class Person implements Comparable<Person>{
        int age;
        String name;

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

        @Override
        public int compareTo(Person person){
            if(person.age < age){
                return 1;
            }else if(person.age > age){
                return -1;
            }
            return 0;
        }

        @Override
        public String toString(){
            return this.age + " " + this.name;
        }
    }

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

        List<Person> list = new ArrayList<>();
        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            list.add(new Person(Integer.parseInt(st.nextToken()), st.nextToken()));
        }

        Collections.sort(list);
        for(Person person : list){
            System.out.println(person);
        }
        
    }
}

 

✔️ counting sort 코드

1. 나이가 1 ~ 200 사이로 입력되므로 StringBuilder배열을 200까지 입력받을 수 있도록 크기 201로 선언한다

2. 각 배열마다 stringbuilder를 생성해준다

3. age를 인덱스로 사용하고, 추후 출력형식에 맞춰 stringbuilder를 append한다

4. StrinbBuilder배열을 돌면서 null이 아니라면 출력한다.

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

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

        StringBuilder[] sbArr = new StringBuilder[201];

        for(int i = 0; i < 201; i++){
            sbArr[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();
            sbArr[age].append(age).append(" ").append(name).append("\n");
        }

        for(StringBuilder str : sbArr){
            if(str != null){
                System.out.print(str);
            }
        }
    }
}

 

두 방법의 시간복잡도 비교

 

위에서부터

1. 배열을 사용한 방법 : 464ms

2. compareTo를 사용한 방법 1600ms

이다

 

📍 기억할 것

compareTo는 시간 복잡도가 매우 안좋은것을 볼 수 있다.

배열을 이용한 countingSort는 O(n+데이터입력크기)이므로 countingSort를 이용할 수 있다면 최대한 사용하는 것이 좋다.