코딩 테스트 [정렬] - 수 정렬하기2

N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오.

---

입력

1번째 줄에 수의 개수 N(1 ⪯ N ⪯ 1,000,000), 2번째 줄부터 N개의 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수다. 수는 중복되지 않는다.

출력

1번째 줄부터 N개의 줄에 오름차순 정렬한 결과를 1줄에 1개씩 출력한다.

예제 입력
5	// 수의 개수
5
4
3
2
1

예제 출력
1
2
3
4
5

---

1단계 - 문제 분석하기

N의 최대 범위가 1,000,000이므로 O(nlogn)의 시간복잡도로 정렬을 수행하면 된다. 병합 정렬로 수행한 후 결과를 출력해보자.

2단계 - 손으로 풀어 보기

1 정렬할 그룹을 최소 길이로 나눈다. 원본 배열의 길이가 5이므로 2, 2, 1 길이로 나눴다. 그 후 나눈 그룹마다 병합 정렬한다. 각 그룹마다 index1, index2를 지정해 비교하면서 정렬 용도로 선언한 tmp배열에 병합 정렬한다.

현재의 경우 그룹이 3개이므로 2번째, 3번째 그룹을 병합했다.

2 이어서 병합된 그룹을 대상으로 정렬한다. 위에서 오른쪽 그룹을 병합할 때는 최초 비교시 index2의 값(1)이 선택되어 뒤 세트가 모두 사용된다, 이런 경우는 남아 있는 세트(앞 세트)의 값(2, 3)을 뒤에 차례대로 적어준다.

3 마지막으로 남은 두 배열을 병합 정렬한다.

3단계 - sudo코드 작성하기

N(정렬할 수 개수)
A(정렬할 배열 선언하기)
tmp(정렬할 때 사용할 임시 배열 선언하기)
for(N만큼 반복) {
	A배열에 저장하기
}

병합 정렬 함수 수행
결괏값 출력

[별도 함수 구현 부분]
병합 정렬(s, e)
{
	s(시작점), e(종료점), m(중간점)
    
    // 재귀 함수 형태로 구현
    병합 정렬(s, m)
    병합 정렬(m+1, e)
    
    for(i : s ~ e) {
    	tmp 배열 저장
	}
    
    // 두 그룹 병합 로직
    index1 -> 앞쪽 그룹 시작점
    index2 -> 뒤쪽 그룹 시작점
    while(index1 <= 중간점 $$ index2 <= 종료점) {
    	양쪽 그룹의 index가 가리키는 값을 비교한 후 더 작은 수를 선택해 배열에 저장하고,
        선택된 데이터의 index값을 오른쪽으로 한 칸 이동하기.
        반복문이 끝난 후 남아있는 데이터 정리하기
    }
}

4단계 - 코드 구현하기

import java.io.*;

public class Q20 {
    public static int[] A, tmp;
    public static long result;
    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());
        A = new int[N];
        tmp = new int[N];
        for(int i = 0; i < N; i++){
            A[i] = Integer.parseInt(br.readLine());
        }

        merge_sort(0,N-1);

        for(int i = 0; i < N; i++){
            bw.write(A[i] + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static void merge_sort(int s, int e){
        if(e - s < 1){
            return;
        }

        int  m = (s + e) / 2;

        merge_sort(s, m);
        merge_sort(m + 1, e);
        for(int i = s; i <= e; i++){
            tmp[i] = A[i];
        }

        int k = s;
        int index1 = s;
        int index2 = m + 1;
        while(index1 <= m && index2 <= e){
            if(tmp[index1] < tmp[index2]){
                A[k] = tmp[index1];
                k++;
                index1++;
            }else {
                A[k] = tmp[index2];
                k++;
                index2++;
            }
        }
        while(index1 <= m){
            A[k] = tmp[index1];
            k++;
            index1++;
        }
        while(index2 <= e){
            A[k] = tmp[index2];
            k++;
            index2++;
        }
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편