백준 2751 - 수 정렬하기 2

문제

시간제한 2초

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

입력

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

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

5
5
4
3
2
1

예제 출력 1

1
2
3
4
5

문제풀이

문제의 N의 최댓값은 1,000,000 이어서 Arrays.sort() 함수를 사용하여 오름차순으로 바꿔준 후 출력하면 되는 문제인줄 알았다.

하지만 시간초과가 나온다??

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

class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];

        for(int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(A);

        for(int i = 0; i < N; i++) {
            System.out.println(A[i]);
        }


    }

}

아무래도 다른 방법을 사용하도록 하기 위해서 시간초과가 나오게 한 것 같다.

그래서 책과 유튜브를 참고하여서 시간복잡도 평균값이 $O(nlogn)$인 병합정렬을 공부하였다.

병합정렬

분할정복 방식을 사용해서 데이터를 분할하고 또 분할해서 분할한 집합을 정렬하며 합치는 알고리즘이라고 한다.
참고 영상 : https://youtu.be/QAyl79dCO_k

이론은 이해가 되었지만 코드에 적용 시키기가 너무나 어려웠다.

코드는 유튜브나 책을 참고하여서 적용시켰는데
하나 하나 코드가 어떤 뜻을 가지고 있는지 정리를 해보기로 하였다. (내가 이해를 잘 못했기 때문에...)

전체 코드

import java.io.*;

public class 수정렬하기2 {

    public static int[] A, tmp;		// 원본 배열 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 + 1];                       
        tmp = new int[N + 1];
        // N + 1 로 한 이유는 인덱스 번호 계산을 쉽게 하기 위해서 ex) A = [0, 5, 4, 3, 2, 1]
        
        for(int i = 1; i <= N; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }

        merge_sort(1, N);                   // 병합 정렬 수행하기

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

    private static void merge_sort(int start, int end) {
        if(end - start < 1)			// end - start < 1 일 경우는 end 가 start 보다 작다는 뜻인데 병합정렬에서는 그럴 경우는 없다.
            return;

        int mid = start + (end - start) / 2;	
        /*
        처음에는 (start + end) / 2 로 작성하였지만 정확한 중앙값이 나오지 않는다.
        ex) start = 1, end = 4 인 경우 중앙은 2가 나와야 한다.
        
        (1 + 4) / 2 = 4 (X) 
        
        1 + (4 - 1) / 2 = 3 (O)
        */
        merge_sort(start, mid);			// 재귀 함수 형태로 구현
        merge_sort(mid + 1, end);		// 재귀 함수 형태로 구현

        for(int i = start; i <= end; i++) {
            tmp[i] = A[i];
        }

        int k = start;
        int part1 = start;
        int part2 = mid + 1;
        /*
        	두 그룹을 병합하기 위한 로직
            part1 과 part2 비교하여서 더 작은 쪽이 A[k] 의 값을 넣어준다.
            
            ex)     
            part1 = 1, part2 = 5, k = part1 = 1
            tmp[part1] = 3 , tmp[part2] = 2
            
            A[k] = tmp[part2];
            k++;
            part2++;
       
            
        */
        while(part1 <= mid && part2 <= end) {	
            if(tmp[part1] < tmp[part2]) {
                A[k] = tmp[part1];
                k++;
                part1++;
            }else {
                A[k] = tmp[part2];
                k++;
                part2++;
            }
        }

		// 한 쪽 그룹이 모두 선택된 경우에 남아 있는 값을 정리하기
        while(part1 <= mid) {
            A[k] = tmp[part1];
            k++;
            part1++;
        }
        while(part2 <= end) {
            A[k] = tmp[part2];
            k++;
            part2++;
        }

    }
}

회고

병합정렬을 어떻게 해야 코드에 적용할수 있는지 계속 공부를 하였다.
아직까지 완벽히 이해했다고 하기에는 부끄럽지만 그래도 이틀동안 코드를 유심히 보고 다른 문제도 풀다보니 어느 정도는 감을 잡게 되었다.
다음 문제인 버블 소트 문제도 같이 풀어보니 이해가 되었다는 점에서 역시 비슷한 문제를 많이 풀어봐야 한다는 또 하나의 깨달음을 얻게되었다.