[Problem Solving/Java] 백준 2751번 - 수 정렬하기 2

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

2751번: 수 정렬하기 2

문제

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

입력

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

출력

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

첫 번째 시도

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

public class Main {
    public static int[] src;
    public static int[] tmp;

    // 병합 정렬 메소드
    public static void mergeSort(int start, int end) { // start는 시작 인덱스, end는 마지막 인덱스
        if (start < end) { // 잘못 들어온 인덱스 거르기
            int mid = (start + end) / 2; // 갖고온 배열의 중간 인덱스
            mergeSort(start, mid); // 재귀함수 처음부터 중간까지
            mergeSort(mid + 1, end); // 재귀함수 중간부터 끝까지
            int p = start;
            int q = mid + 1;
            int idx = p;
            // 안정 정렬이기 때문에 index를 유지 p가 mid 이하이거나, end 이하일 때 동작해야함
            // 미만이 아닌 이유는 원소의 개수가 1개일 때까지 쪼개기 때문
            while (p <= mid || q <= end) {
                // 첫 번째 분할(start부터 mid까지)에서 원소를 가져오는 경우
                // 1. 두 번째 분할의 원소를 이미 다 가져온 경우 (q>end)
                // 2. 첫 번째 분할에서 가져오지 않은 원소가 있고, 첫번째 분할의 첫 원소 값이 두 번째 분할의 첫 원소 값보다 작은 경우
                if (q > end || (p <= mid && src[p] <= src[q])) {
                    tmp[idx++] = src[p++];
                } else {
                    tmp[idx++] = src[q++];
                }
            }
            // 재 배열한 배열을 src배열에 복사
            if (end + 1 - start >= 0) System.arraycopy(tmp, start, src, start, end + 1 - start);
        }
    }

    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());
        src = new int[n];
        tmp = new int[n];
        for (int i = 0; i < n; i++) {
            src[i] = Integer.parseInt(br.readLine());
        }
        mergeSort(0, src.length - 1);
        for (int i = 0; i < n; i++) {
            bw.write(src[i] + "\n");
        }
        bw.flush();
        bw.close();
    }
}

해결 방법

병합 정렬 알고리즘으로 구현했다. mergeSort 메소드로 배열의 시작 인덱스와 끝 인덱스를 불러온다. 중간의 인덱스를 저장할 mid를 선언 후 반으로 나누는 것을 배열의 크기가 1이 될 때까지 재귀함수를 통해 반복한다. 배열이 다 나뉘는 것을 p와 q를 사용하여 인덱스로 구현한다., 시작점에서 시작하는 p와 중간지점에서 시작하는 q가 인접한 배열을 비교하여 순서를 바꾼다. 순서를 바꿀 땐 임시로 저장할 tmp 배열에 원소 값을 비교해서 넣는다. 이때 인덱스는 이전 배열의 인덱스를 초과하지 않는다. if문을 통해 인덱스가 p인 배열(분할된 첫번째 배열)의 원소 값이 인덱스가 q인 배열(분할된 두 번째 배열)의 원소값보다 작으면 tmp배열에 p인 배열 즉 왼쪽 배열의 값을 넣고 아니면 오른쪽 배열(인덱스가 q)의 값을 넣는다. 재배열한 배열을 다시 출력한다. 

어려웠던 점 / 고쳐야할 점

제출 시 시간초과가 있었는데, System.out.print를 통해 출력해서 그렇다는 질문 글이 있어서, BufferedWriter로 출력하니 문제없이 통과했다.