[JAVA] 백준 10814번 【나이순 정렬】

---

이 문제도, 다른 정렬 문제와 비슷하다.

 

처음에, Member 클래스를 생성한 뒤, Comparable을 implements 한 다음

 

나이가 같다면, 맴버 아이디를 비교하고, 나이가 다르다면, 나이를 기준으로 오름차순 되게끔 compareTo()를 정의한 후

 

List<Member> memberList = new ArrayList<>(); 를 선언해서 Member 타입의 객체들을 기록한 뒤,

 

Collections.sort()를 사용해서 정렬하였다.

 

그리고 출력 시, [나이 이름] 이 출력되야 하므로, toString()을 오버라이딩하였다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        //회원들의 나이가 증가하는 순으로
        // 나이가 같다면 먼저 가입한 사람이 앞에 오는 순으로
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.valueOf(br.readLine());
        List<Member> memberList = new ArrayList<>();
		//Collections.sort() 를 사용하기 위해 List에 Member객체 저장
        
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            memberList.add(new Member(Integer.valueOf(input[0]), input[1],i));
        }
		각 Member객체에 나이, 이름, 등록순서를 생성한 뒤, 리스트에 저장

//        for (Member member : memberList) {
//            System.out.println("member = " + member);
//        }
        Collections.sort(memberList);

        for (Member member : memberList) {
            System.out.println(member);
        }


    }
}

class Member implements Comparable<Member> {

    private int age,memberId;
    private String name;


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

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

    @Override
    public int compareTo(Member m1) {
        if (this.age == m1.age) { //나이가 같다면
            return this.memberId - m1.memberId; //등록 순서로 확인
        }else if(this.age!= m1.age){ //나이가 다르다면
            return this.age - m1.age; //나이로 확인
        }
        return -1;
    }

}

하지만, 시간이 오래 걸린 것 같아, 다른 분들의 코드를 참고했더니 이 문제에서 StringBuilder를 사용하면 획기적으로 속도가 빨라지는 사실을 알았다.

 

---

먼저 StringBuilder sb = new Stringbuilder(); 를 만드는데, 마지막에 System.out.println(sb) 한번으로 출력하게 하기 위한 StringBuilder이다.

 

그리고 각 인덱스에 StringBuilder 객체를 넣을 수 있는 StringBuilder [] 배열을 만든다.

 

int 배열은 int[] arr = new int[3]; 와 같이 생성하듯이

 

StringBuilder 배열도 StringBuilder[] stringBuilderArray = new StringBuilder[201]; 로 생성한다.

 

참고로 크기가 201인 이유는, 문제에서 나이가 1살에서 200살까지로 주어진다고 해서,

 

나이를 StringBuilder배열의 인덱스로 하기 위함이다.

 

첫 for문을 통해서 StringBuilder 배열을 StringBuilder 객체로 채워준다.

 

객체가 채워져있지 않으면, 마지막 출력 시 null값이 나올 수 있기 때문이다.

 

그리고 StringBuilder[age]에 해당 age에 일치하는 데이터를 append 한다.

 

만약

19 최맹구

20 김철수

20 박짱구

 

데이터가 입력된다면

 

StringBuilder[19] 에 있는 StringBuilder에 "19 최맹구\n" 가 입력되어있을 것이고

StringBuilder[20] 에 있는 StringBuilder에 "20 김철수\n20 박짱구\n" 가 입력되어있을 것이다.

 

그리고 마지막 for문을 통해서 처음에 생성했던 StringBuilder sb 에 인덱스 순서로 append 하면

 

"19 최맹구\n20 김철수\n20 박짱구\n"

 

가 입력될 것이다.

 

이는 나이 오름 차순으로 정렬되어 있으며, 나이가 같은 경우 자동으로 회원 등록 순으로 정렬이 된다.

 

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

public class Main{
    public static void main (String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder(); //마지막출력용 StringBuilder

        StringBuilder[] stringBuilderArray = new StringBuilder[201];
        for (int i = 0; i < 201; i++){
            stringBuilderArray[i] = new StringBuilder();
            // StringBuilder 배열에 하나씩 StringBuilder 객체를 넣어주지 않으면 마지막에 한번에 출력할때, null 값이 나온다.
            // 하지만, 위와 같이 객체를 하나씩 채워넣어주면, 아무 데이터가 채워지지 않았을 때에도 null 값이 출력 안된다.
        }

        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++){
            String[] input = br.readLine().split(" ");
            int age = Integer.valueOf(input[0]);
            String name = input[1];
            stringBuilderArray[age].append(age+" "+name).append("\n");
        }

        for (StringBuilder k : stringBuilderArray){
            sb.append(k);
        } //입력된 데이터들을 쌓음, 나이가 인덱스로서 순서대로 입력되어있으므로, for-each문을 사용하면, 나이순으로 나오고
        // 나이가 같다면 등록 순으로 나올 것

        System.out.println(sb);

    }

}

 

속도가 1616ms 에서 680ms 로 획기적으로 감소했다.

 

이런 발상을 할 수 있는게 참 신기한 것 같다.

 

이래서 알고리즘을 많이 풀어보라고 하는구나 싶다.