[백준 알고리즘][자바] 10814번 : 나이순 정렬

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

10814번: 나이순 정렬

이번 문제는 안정 정렬(Stable Sort)에 관한 문제입니다.

입력으로 사람들의 나이와 이름이 가입한 순서대로 주어집니다. 이때 회원들을 나이순으로 정렬하고, 나이가 같으면 먼저 가입한 사람이 앞에 오도록 정렬해야 합니다.

 

안정 정렬(Stable Sort)이란 정렬을 마쳤을 때 동일한 키값을 가진 요소의 순서가 유지되는 것을 의미합니다.

예를들어, 1, 3, 5, 7, 3 를 정렬한다면

정렬 후에 1, 3, 3, 5, 7 처럼 3의 순서가 유지된다면 안정 정렬

정렬 후에 1, 3, 3, 5, 7 처럼 3의 순서가 바뀐다면 불안정 정렬입니다. 안정 정렬은 대표적으로 버블 정렬, 삽입 정렬, 병합 정렬등이 있습니다.

 

이번 문제에서는 안정 정렬중 시간 복잡도가 제일 빠른 병합정렬을 사용하여 해결하였습니다.

2022.07.06 - [Algorithm/Theory] - [Java] 병합 정렬(Merge Sort)

[Java] 병합 정렬(Merge Sort)

 

 

풀이

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

public class Main {
	
	static Member[] buff;

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine()); // 단어의 개수
		Member[] mem_array = new Member[N];
		
		for(int i = 0 ; i < N ; i++) {
			String member = br.readLine();
			mem_array[i] = new Member(Integer.parseInt(member.split(" ")[0]), member.split(" ")[1]);
		}

		mergeSort(mem_array, N);
		
		for(int i = 0; i < N; i++) {
            bw.write(mem_array[i].Age + " " + mem_array[i].Name + "\n");
        }
	
		br.close();
		bw.flush();
		bw.close();
	}	
	
	static void merge(Member[] a, int left, int right) {
		if(left < right) {
			int i;
			int center = (left + right) / 2;
			int p = 0;
			int j = 0;
			int k = left;
			
			merge(a, left, center);      // 재귀 호출을 통해서 앞부분 병합 정렬(잘게 쪼개줌).
			merge(a, center + 1, right); // 재귀 호출을 통해서 뒷부분 병합 정렬(잘게 쪼개줌).
			
			for(i = left; i <= center; i++) {
				buff[p++] = a[i]; // buff에 center 기준 왼쪽 배열 저장
			}
			
			while(i <= right && j < p) { // i = center + 1
				a[k++] = (buff[j].Age <= a[i].Age) ? buff[j++] : a[i++];
			}
			
			while(j < p) { // 나머지 값 복사
				a[k++] = buff[j++];
			}
		}
	}
	
	static void mergeSort(Member[] a, int n) {
		buff = new Member[n];
		
		merge(a, 0, n-1);
		
		buff = null;
	}
	
}

class Member {
    public int Age;
    public String Name;

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