[백준] 10814번 : 나이순 정렬(JAVA)

정렬 마스터 은구.gif

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

10814번: 나이순 정렬

위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 12단계

 

정렬의 카테고리에 포함되어 있는 문제이다.

 

입력은 회원의 수가 입력되고 회원의 수 만큼

 

회원의 나이와 이름이 순서대로 입력된다.

 

입력된 값들을 나이 순서대로 정렬하는데,

 

나이가 같으면 먼저 입력받은 순서대로 정렬을 해야한다.

 

정렬을 해도 입력된 순서가 바뀌지 않은 정렬을 Stable sort라고 하며

 

대표적인 안정정렬 알고리즘으로는 버블, 삽입, 합병, 기수정렬이 있다.

 

나는 이 방법 중 합병 정렬을 사용하였다.

 

import java.io.*;

class Member {
    public int Age;
    public String Name;

    public Member(int Age, String Input) {
        this.Age = Age;
        Name = Input;
    }
}

class Merge {
    Member[] temp;
    public void Init(int N) {
        temp = new Member[N];
    }

    public void Merge_Sort(Member[] x, int left, int right) {
        int mid;
        if(left < right) {
            mid = (left + right) / 2;
            Merge_Sort(x, left, mid);
            Merge_Sort(x, mid + 1, right);
            Merge_Last(x, left, mid, right);
        }
    }

    public void Merge_Last(Member[] x, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = left;

        while(i <= mid && j <= right) {
            if(x[i].Age < x[j].Age)
                temp[k++] = x[i++];
            else if(x[i].Age == x[j].Age)	//나이가 같을 때, 먼저 입력된 순서대로 정렬
                temp[k++] = x[i++];
            else
                temp[k++] = x[j++];
        }

        while(i <= mid)
            temp[k++] = x[i++];

        while(j <= right)
            temp[k++] = x[j++];

        for(int index = left; index < k; index++)
            x[index] = temp[index];

    }
}

public class Question_10814 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        Member[] MB = new Member[N];

        for(int i = 0; i < N; i++) {
            String[] Input = br.readLine().split(" ");
            int Age = Integer.parseInt(Input[0]);
            MB[i] = new Member(Age, Input[1]);
        }

        Merge mg = new Merge();
        mg.Init(N);

        mg.Merge_Sort(MB, 0, MB.length - 1);

        for(int i = 0; i < N; i++) {
            bw.write(MB[i].Age + " " + MB[i].Name + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}