[코딩테스트 챌린지] 백준 10814 나이순 정렬 (java)

문제

 

문제 탐색하기

 

1. 정렬 조건 확인하기

input 값은 최대 10만이고 나이와 이름이 가입한 순서대로 주어진다고 합니다. 나이는 오름차순으로 정렬하고 나이가 같을 경우 가입한 시기를 오름차순으로 정렬해야하는 조건이 주어졌습니다. 

java 의 대표적인 정렬 클래스인 Arrays.sort()를 사용하면 시간복잡도가 평균적으로는 O(nlog(n)) 이지만 최악의 경우 O(n^2)의 시간복잡도를 가진다 합니다. 또다른 정렬클래스인 Collections.sort() 를 사용하면 시간복잡도는 O(nlog(n))이고 정렬조건을 custom 할 수 있는 이점이 있습니다. 따라서 Collections를 활용하여 데이터를 정렬시킬 것 입니다.

 

2. 입력값을 저장하는 객체 생성

input 값은 나이와 이름이 공백을 사이에 두고 주어집니다. 정렬 조건을 만족시키기 위해서는 가입한 순서도 고려되어야 합니다. 따라서 이 3가지 변수를 저장할 객체를 생성하여 사용할 것 입니다.

객체는 나이, 이름, 가입순서 이 3가지 변수를 저장하도록 만들고 나이와 이름은 input 값에서 공백으로 split하여 객체에 저장합니다. 시퀀스는 input값을 받아올때의 시퀀스를 증가시키며 저장하면 가입 순서도 저장할 수 있습니다.

 

3. 출력

최종적으로 값을 출력할 때 나이와 이름을 공백을 사이에 두고 입력 값 처럼 출력합니다. 2번에서 생성한 객체의 toString 메소드를 오버라이드하여 객체에 저장되어있는 나이와 이름을 출력하면 됩니다.

 

코드 설계하기

1.  온라인 저지 회원 수 입력
2.  입력받은 한 줄을 공백으로 split해서 객체에 저장
   • 입력 값을 저장하기 위한 객체 생성 = UserDao
3.  생성된 객체를 list에 저장
4.  Collections.sort() 함수의 두번째 인자에 new Comparator를 선언하여 정렬 메소드 오버라이드해서 구현
   1. 나이로 오름차순 정렬
   2. 나이가 같을 경우 가입한 순서대로 오름차순 정렬
5.  객체의 toString 메소드를 custom하여 원하는 형태로 출력

 

시도 회차 수정 사항

1회차) 객체를 먼저 선언하고 그 객체에 값을 변경하는 식으로 진행하려 했는데 다 동일한 객체를 저장하게 되는 이슈가 생겼습니다,, 따라서 새롭게 입력값을 받을때마다 새로운 객체를 선언해서 list에 저장하는 식으로 변경했습니다.

 

2회차) Collections.sort()를 사용해야한다는 것은 알았지만 정렬메소드를 구현하는 부분을 잘 몰라서 공부하면서 진행하였습니다.

 

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class OrderingByAge {

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

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int count = Integer.parseInt(reader.readLine()); // 1. 온라인 저지 회원 수 입력

        List<UserDao> list = new ArrayList<>();
        for(int i=0; i<count; i++){
            // 2. 입력받은 한 줄을 공백으로 split해서 객체에 저장
            String[] arr = reader.readLine().split(" ");
            UserDao user = new UserDao(Integer.parseInt(arr[0]), arr[1], i);

            // 3. 생성된 객체를 list에 저장
            list.add(user);
        }

        // 4. collections 를 통해서 정렬 구현
        Collections.sort(list, new Comparator<UserDao>() {
            @Override
            public int compare(UserDao o1, UserDao o2) {

                // 4-1. 나이로 오름차순 정렬
                if(o1.age == o2.age){
                    // 4-2. 나이가 같을 경우 가입한 순서대로 오름차순 정렬
                    if(o1.seq >= o2.seq){
                        return 1;
                    }else{
                        return -1;
                    }
                }else if(o1.age > o2.age){
                    return 1;
                }else{
                    return -1;
                }
            }
        });

        // 5. 객체의 toString 메소드를 custom하여 출력
        for(UserDao obj : list){
            System.out.println(obj.toString());
        }

    }

    // # 입력받는 값을 저장하는 객체 생성
    static class UserDao{
        private int age;
        private String name;
        private int seq;

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

        // # 출력 형식에 맞게 toString 메소드 설정 '나이 이름'
        @Override
        public String toString() {
            return age + " " + name;
        }
    }


}