[백준] 2751 - K번째 수 (2)

👉🏻 백준 2751 문제 바로가기

❓ 병합 정렬?!

병합 정렬: 분할 정복 방식을 사용해 데이터를 분할하고, 분할한 집합을 정렬하며 합치는 알고리즘
평균적인 시간 복잡도는 O(nlogn).

❗️pseudo code

❗️pesudo code

count (정렬할 수 개수)
sortedArray (정렬할 배열)
tempArray (정렬 시 잠시 사용 할 임시 배열)

for (count 만큼 반복) {
    sortedArray 선언
}
병합 정렬 함수 수행
결괏값 출력

// 병합 정렬 수행
병합 정렬 (start, end) {
    start(시작점), end(종료점), middle(중간점)

    // 재귀 함수 형태로 구현
    병합 정렬 (start, middle)
    병합 정렬 (middle + 1, end)
    for (start ~ end) {
        tempArray 저장
    }

    // 두 그룹 병합 로직
    index1 (앞쪽 그룹 시작점)
    index2 (뒤쪽 그룹 시작점)
    while (index1 <= 중간점 && index2 <= 종료점) {
        양쪽 그룹 index가 가르키는 값을 비교한 후 더 작은 수를 선택해 배열에 저장하고,
        선택된 데이터의 index 값을 오른쪽으로 한 칸 이동하기
        반복문이 끝난 후 남아 있는 데이터 정리
    }
}

✨ solve

import java.io.*;

public class Main {
    public static int[] sortedArray, tempArray;
    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 count = Integer.parseInt(br.readLine());
        sortedArray = new int[count + 1];
        tempArray = new int[count + 1];
        for (int i = 1; i <= count; i++) {
            sortedArray[i] = Integer.parseInt(br.readLine());
        }

        // 병합 정렬 수행
        mergeSort(1, count);
        for (int i = 1; i <= count; i++) {
            bw.write(sortedArray[i] + "\n");
        }
        bw.flush();
        bw.close();
    }

    private static void mergeSort(int start, int end) {
        if (end - start < 1) {
            return;
        }
        int middle = start + (end - start) / 2;

        // 재귀 함수 형태로 구현
        mergeSort(start, middle);
        mergeSort(middle + 1, end);
        for (int i = start; i <= end; i++) {
            tempArray[i] = sortedArray[i];
        }
        int k = start;
        int index1 = start;
        int index2 = middle + 1;

        // 두 그룹 병합
        while (index1 <= middle && index2 <= end) {
            if (tempArray[index1] > tempArray[index2]) {
                sortedArray[k] = tempArray[index2];
                k++;
                index2++;
            } else {
                sortedArray[k] = tempArray[index1];
                k++;
                index1++;
            }
        }
        while (index1 <= middle) {
            sortedArray[k] = tempArray[index1];
            k++;
            index1++;
        }
        while (index2 <= end) {
            sortedArray[k] = tempArray[index2];
            k++;
            index2++;
        }
    }
}