[백준]2751 - 병합정렬(Java)

 

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

2751번: 수 정렬하기 2

풀이

해당 문제는 단순 정렬 문제이다. 하지만 정렬에는 종류가 아주 많다는거^^...

 

병합정렬로 풀이를 제출하면서 이전에 제출 기록이 있길래 코드를 살짝 봤더니...핰ㅋㅋㅋㅋㅋㅋㅋ그냥 ArrayList로 입력받은 값들을 넣은 다음 Collection.sort로 아주 간단하게 해결해버렸다...ㅎㅎ 편함을 추구한 과거의 나 반성하자

 

아무튼 병합정렬은 무엇이냐 하면 수열이 있을 때 중간 값을 기준으로 왼쪽 오른쪽으로 나누고(분할) 나눈 배열을 정렬해가면서(정복) 합치는 정렬이라고 보면된다. 무슨 말인지는 사진을 보면 더 이해가 쉽다. 

출처 : 위키피디아 https://en.wikipedia.org/wiki/Merge_sort

이런식으로 분할을 하고 분할된 값들끼리 정렬을 해나가면서 합치는 원리라고 보면된다. 그리고 우린 이걸 코드로 구현하면 된다. 

 

코드

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

//문제 풀이용
public class Main {

    static int[] tmp, arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        arr = new int[n];
        tmp = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());
        }

        mergeSort(0, arr.length - 1);
        StringBuilder sb = new StringBuilder();
        for (int v : arr) {
            sb.append(v).append("\n");
        }
        System.out.println(sb);
    }

    private static void mergeSort(int start, int end) {
        if (start < end) {
            int mid = (start + end) / 2;   //중간 인덱스
            mergeSort(start, mid);         //왼쪽 분할
            mergeSort(mid + 1, end);       //오른쪽 분할

            int lt = start;       //왼쪽 시작값
            int rt = mid + 1;     //오른쪽
            int idx = lt;         //임시배열 시작인덱스

            //왼쪽 인덱스 값이 중간값보다 작거나 같을경우 && 오른쪽 인덱스 값이 끝보다 작거나 같을경우
            while (lt <= mid && rt <= end) {
                //왼쪽이 더 작을때 왼쪽 값 넣어주기
                if (arr[lt] <= arr[rt]) tmp[idx++] = arr[lt++];
                //오른쪽이 더 작을때 오른쪽 값 넣어주기
                else tmp[idx++] = arr[rt++];
            }

            //왼쪽이 다 정렬된 경우
            if (lt > mid) {
                //남은 오른쪽 값 tmp에 채워주기
                for (int i = rt; i <= end; i++) tmp[idx++] = arr[i];
            }
            //오른쪽이 다 정렬된 경우
            else {
                //남은 왼쪽 배열 값을 tmp에 채우기
                for (int i = lt; i <= mid; i++) tmp[idx++] = arr[i];
            }

            //임시배열 tmp에 있는값 원래 arr배열에 넣어주기
            for (int i = start; i <= end; i++) arr[i] = tmp[i];
            
        }
    }
}

참고로 탑-다운 방식으로 풀었으며 바텀-업 방식으로도 가능하다. 주석들을 보면서 {2,1,4,3}을 입력으로 받았을 때 코드를 설명해보자면 우선 시작은 분할이다. 

메인에서 아래 코드를 호출하면 0, 3 이 입력으로 들어간다. 

mergeSort(0, arr.length - 1);

start = 0 / end = 3 / mid = 1 -> mergeSort(0,1)을 호출 

start = 0 / end = 1 / mid = 0 -> mergeSort(0,0)일 경우 아무 실행을 하지 않고 종료 후 mergeSort(1,1) 호출이지만 이거또한 조건에 걸리지 않기 때문에 종료 후  아래 로직 실행 

 

lt, rt는 각각 왼쪽 배열의 시작 값과 오른쪽 배열의 시작 값으로 분할된 배열 두개를 비교할 때 사용한다. 

즉 위 사진에서 2 1로 찢어진 경우 왼쪽 배열은 2 오른쪽 배열은 1이고 해당 두 배열의 시작값은 lt = start가 될거고 rt = 중간값 + 1이 될것이다. 그래야 왼쪽 오른쪽 배열로 찢어지는 것을 의미하기 때문이다. 

 while (lt <= mid && rt <= end) {
        //왼쪽이 더 작을때 왼쪽 값 넣어주기
        if (arr[lt] <= arr[rt]) tmp[idx++] = arr[lt++];
        //오른쪽이 더 작을때 오른쪽 값 넣어주기
        else tmp[idx++] = arr[rt++];
    }

    //왼쪽이 다 정렬된 경우
    if (lt > mid) {
        //남은 오른쪽 값 tmp에 채워주기
        for (int i = rt; i <= end; i++) tmp[idx++] = arr[i];
    }
    //오른쪽이 다 정렬된 경우
    else {
        //남은 왼쪽 배열 값을 tmp에 채우기
        for (int i = lt; i <= mid; i++) tmp[idx++] = arr[i];
    }

    //임시배열 tmp에 있는값 원래 arr배열에 넣어주기
    for (int i = start; i <= end; i++) arr[i] = tmp[i];
}

그 다음 lt의 값이 중간값보다 작거나 같을 경우와 rt의 값이 end값보다 작거나 같을 경우 수행하며 각각lt, rt의 위치에 있는 값들을 비교하여 tmp에 할당하면서 idx 값과 각각의 위치값을 증가시켜 준다. 

 

while문을 타지 않았을 때 lt 값과 rt 값 중 어디 한 곳은 분명 끝에 도달하지 못했을테니 도달하지 못한 배열들의 값을 tmp[idx]값에 할당해주고 마지막으로 tmp의 정렬된 값들을 arr에 할당해주면 정렬이 완료된다.