백준 문제풀이(49) 수 정렬하기2 병합정렬

 

그냥 원하는 정렬 알고리즘 아무거나 연습하기 좋은 수 정렬하기 문제다.

그리고 난 옛날에 병합 정렬을 공부하다가 어려워서 때려치운 전적이 있다.

따라서 오늘은 병합 정렬이다.

 

우선 merge sort에 대해 간단하게 알아보고 넘어가자. 자세한 건 직접 찾아보삼

 

 

 

정말 이 그림대로 정렬한다.

우선 재귀를 이용해 최소단위까지 쪼갠 뒤, 수의 크기에 따라 정렬하며 다시 합치면 된다.

 

그리고 quickSort와 가장 큰 차이점이라면 mergeSort는 기존 배열에서 바로 재정렬하는 것이 아닌 추가 배열을 생성해서 해당 배열에서 먼저 정렬한 뒤 기존 배열에 적용하는 방식이다.

 

이런 형태다.

 

mergeSort (배열, 인덱스작은놈, 인덱스큰놈) {

if (인덱스작은놈 != 큰놈) {

int 중간인덱스;

mergeSort(배열, 인덱스작은놈, 중간)

mergeSort(배열, 중간, 인덱스큰놈)

merge(배열, 작은놈, 중간, 큰놈)

}

}

 

merge (배열, 작은놈, 중간놈, 큰놈) {

int index = 작은놈

int l = 작은놈

int r = 큰놈

 

while (l < 중간 && r < 큰놈) {

if (배열[l] > 배열[r]) {

임시배열[index++] = 배열[r] }

else {

임시배열[index++] = 배열[l]

}

 

..

 

쉽죠?

재귀 개념을 이용한 정렬 알고리즘을 사용해본 적이 있다면 여기까지만 봐도 어떻게 해야할지 감이 올 것이다.

안 풀어봤으면.. 유튜브 보고 배우자

 

그다지 어려운 개념이 아니라서 이해하는데 큰 어려움은 없겠지만, 많은 재귀 문제가 그렇듯 중간에 변수명 하나 잘못 쓰는 순간 돌이킬 수 없는 수렁에 빠지고 만다.

내가 지금 그러다가 2시간 날리고 왔다.

 

시간 내다 버리고 깨달은 것은 왜 사람들이 알고리즘 문제 풀 때 파라미터(인자) 는 풀네임으로 받아오고 함수 내부에서 선언하는 지역 변수는 l, r같은 축약형으로 작성하는지에 대한 것이다..

그렇게 풀어야 실수 확률이 확연하게 줄어든다.

 

나같이 left, low, right, high 이런 식으로 섞어서 쓰고 어디서 틀렸는지 못찾아서 시간 버리는 행동 하지 말자..

아무튼 정답은 아래에 있다

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
 
        int[] arr = new int[N];
        int[] temp = new int[N];
        
        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        mergeSort(arr,0,arr.length-1,temp);
 
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<N; i++) {
            sb.append(arr[i]).append("\n");
        }
 
        System.out.println(sb.toString());
    }
 
    private static void mergeSort(int[] arr, int low, int high, int[] temp) {
        if (low!=high) {
            int mid = (low+high)/2;
            mergeSort(arr, low, mid, temp);
            mergeSort(arr, mid+1, high, temp);
            merge(arr, low, high, temp);
        }
    }
 
    private static void merge(int[] arr, int low, int high, int[] temp) {
        int mid = (high+low)/2;
        int left = low;
        int index = low;
        int right = mid+1;
 
        while (left<=mid && right<=high) {
            if (arr[left] >= arr[right]) {
                temp[index++] = arr[right++];
            } else {
                temp[index++] = arr[left++];
            }
        }
 
        if (left>mid) {
            while (index<=high) {
                temp[index++] = arr[right++];
            }
        }
 
        if (right>high) {
            while (index<=high) {
                temp[index++] = arr[left++];
            }
        }
        
        for (int i=low; i<=high; i++) {
            arr[i] = temp[i];
        }
    }