Inor

[백준] 10814번 나이순 정렬 본문

Algorithm/백준

[백준] 10814번 나이순 정렬

Inor 2018. 2. 1. 18:48

- 문제 : https://www.acmicpc.net/problem/10814


 주어진 회원들의 나이 순으로 정렬하고 나이가 같을 경우에는 먼저 등록한 순서로 정렬하는 문제 입니다. 등록한 순서는 입력 순서와 동일합니다.




- 풀이


 단순하게 나이 순서로 정렬 해주고 입력 순서를 저장했다가 입력 순서대로 정렬해주면 되는 문제인줄 알았습니다. 그래서 퀵 정렬을 2번 사용해서 나이순으로 먼저 정렬해주고, 나이가 같은 배열을 전체 배열에서 left와 right 인덱스로 나눠서 등록 순서로 배열해주었습니다.

 그런데 문제를 풀다보니 계속 틀렸다고해서 인터넷을 찾아봤습니다. 알고보니 stable sort라는 것이 있었고 stable sort는 같은 값일 경우에 순서를 바꾸지 않고 정렬해주는 방법이었습니다. 3 2 1 4 5 1 이 있을 경우에 1 1 2 3 4 5로 정렬 되는데, stable sort는 1 1 2 3 4 5와 같이 정렬 후에도 빨간색 1이 초록색 1보다 앞에 위치하는 것을 보장합니다. 퀵 정렬은 stable sort를 하기 위해서 기본 로직에 stable sort를 위한 로직을 추가해야합니다. 그래서 합병 정렬로 구현했습니다. 합병 정렬로 나이에 맞게 정렬 해주면 기본적으로 등록 순서는 stable sort에서 보장해줍니다.


 코드에서 Person 클래스는 등록 순서에 맞게 퀵 정렬을 구현해주려고 만들었던 클래스인데 합병 정렬로 변경하면서 삭제하지 않고 그냥 사용했습니다.




- 코드


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

public class SortingByAge {
	BufferedReader br;
	int n;
	Person[] persons;
	Person[] sortedAge, sortedOrder;

	void setValues() {
		br = new BufferedReader(new InputStreamReader(System.in));
		String[] str;
		Person tempPerson;
		try {
			n = Integer.parseInt(br.readLine());
			persons = new Person[n];
			sortedAge = new Person[n];
			sortedOrder = new Person[n];
			for (int i = 0; i < n; i++) {
				str = br.readLine().split(" ");
				tempPerson = new Person();
				tempPerson.age = Integer.parseInt(str[0]);
				tempPerson.name = str[1];
				tempPerson.order = i;
				persons[i] = tempPerson;
			}
		} catch (NumberFormatException | IOException e) {
			e.printStackTrace();
		}
	}
	public void mergeSortAge(int start, int end) {
		int middle;
		if(start < end){
			middle = (start + end) / 2;
			mergeSortAge(start, middle);
			mergeSortAge(middle + 1, end);
			mergeAge(start, middle, end);
		}
	}
	
	public void mergeAge(int start, int middle, int end){
		int left, right, copyIndex, elseIndex;
		left = start;
		right = middle + 1;
		copyIndex = start;
		
		while(left <= middle && right <= end){
			if(persons[left].age <= persons[right].age){
				sortedAge[copyIndex] = persons[left++];
			}else{
				sortedAge[copyIndex] = persons[right++];
			}
			copyIndex++;
		}
		
		if(left > middle){
			for(elseIndex = right; elseIndex <= end; elseIndex++, copyIndex++){
				sortedAge[copyIndex] = persons[elseIndex];
			}
		}else{
			for(elseIndex = left; elseIndex <= middle; elseIndex++, copyIndex++){
				sortedAge[copyIndex] = persons[elseIndex];
			}
		}
		
		for(elseIndex = start; elseIndex <= end; elseIndex++){
			persons[elseIndex] = sortedAge[elseIndex];
		}
	}

	void solve() {
		setValues();
		mergeSortAge(0, persons.length - 1);

		for (int i = 0; i < persons.length; i++) {
			System.out.println(persons[i].age + " " + persons[i].name);
		}
	}

	public static void main(String[] args) {
		SortingByAge m = new SortingByAge();
		m.solve();
	}

	class Person {
		int age;
		String name;
		int order;
	}
}


'Algorithm > 백준' 카테고리의 다른 글

[백준] 10798번 세로읽기  (0) 2018.01.31
[백준] 12761번 돌다리  (0) 2018.01.31
[백준] 1992번 쿼드트리  (0) 2018.01.28
[백준] 2573번 빙산  (0) 2018.01.12
[백준] 1963번 킹  (0) 2018.01.11
Comments