[백준]24060: 병합 정렬(재귀)

레전드 문제였습니다. 레전드. 레전드. 개레전드 에헿이~

일주일이 뭐야 거진 한달이 걸렸네요. 완벽 풀이 들어가보겠습니다.

---

자 우선, 병합정렬이란 ㅁㅜㅇㅓㅅㅇㅣㄹㄲㅏ??????????????????????????

https://st-lab.tistory.com/233

자바 [JAVA] - 합병정렬 / 병합정렬 (Merge Sort)

항상 깊은 감사를 표합니다. 너무나도 큰 도움이 됩니다.

---

자 이렇게,

배열이 있다면 반으로 쪼갠다.

반으로 쪼갠걸 반으로 쪼갠다.

반으로 쪼갠걸 반으로 쪼갠다.

반으로 쪼갠걸 반으로 쪼갠다.

반으로 쪼갠걸 반으로 쪼갠다.

반으로 쪼갠걸 반으로 쪼갠다.

......

 한개가 남을때까지 무한 반복한다.

한개가 남는다면 이제 위로 return,,return,,return,,하면서

왼쪽과 오른쪽의 값을 비교하여 정렬한다.

합치면서 올라간다.

---

자 우선, 이 문제를 풀기 위해서는 병합정렬에 대한 이해를 해야했꼬  이 문제를 풀기 위한 메서드에 들어있는 재귀문을 이해해야했다. merge_sort하는 메서드는 앞에서 설명한대로, 나누는것과 합치는 메서드를 구현해야한다.

이제 내가 작성한 코드를 보여주겠따.

---

package reculsive;

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

public class MergeSort {
    static int[] sorted;
    static int staticK;
    static int cnt;
    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());
        staticK = Integer.parseInt(st.nextToken());
        int[] a = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        merge_sort(a);
        if (cnt < staticK) {
            System.out.println(-1);
        }

    }

    public static void merge_sort(int[] a) {
        sorted = new int[a.length];
        merge_sort(a, 0, a.length - 1);
    }

    public static void merge_sort(int[] a, int left, int right) {
        if (left == right) {
            return;
        }
        int mid = (left + right) / 2;
        merge_sort(a, left, mid);
        merge_sort(a, mid+1, right);
        merge(a, left, mid, right);

    }

    public static void merge(int[] a, int left, int mid, int right) {
        int idx = left;
        int l = left;
        int r = mid + 1;
        while (l <= mid && r <= right) {
            if (a[l] <= a[r]) {
                sorted[idx] = a[l];
                l++;
                idx++;
            } else {
                sorted[idx] = a[r];
                r++;
                idx++;
            }
        }

        if (l > mid) {
            while(r<=right){
                sorted[idx] = a[r];
                idx++;
                r++;
            }
        } else{
            while (l <= mid) {
                sorted[idx] = a[l];
                idx++;
                l++;
            }
        }
        for (int i = left; i <= right; i++) {
            cnt++;
            a[i] = sorted[i];
            if (cnt == staticK) {
                System.out.println(a[i]);
                return;
            }
        }
    }
}

---

 

매우 길어서 이해하기가 쉽지 않을 것이다. 쪼개서 이해해보겠다.

---

우선 static변수로 int형 배열인 sorted, int형 변수인 staticK와 cnt를 선언해주었다.

sorted배열은 merge한 배열을 원래 배열이 a에 옮겨주는 역할을 해줄 것이고 staticK와 cnt는 매서드내부에서 사용자의 입력에 따라 값을 비교해주기 위해서 선언해주었다.

---

public static void merge_sort(int[] a) {
    sorted = new int[a.length];
    merge_sort(a, 0, a.length - 1);
}

public static void merge_sort(int[] a, int left, int right) {
    if (left == right) {
        return;
    }
    int mid = (left + right) / 2;
    merge_sort(a, left, mid);
    merge_sort(a, mid+1, right);
    merge(a, left, mid, right);
}

우리가 입력받는 배열을 a로 받아오면 merge_sort(a) 이런 식으로 넣어줘야지 보기가 매우 편하다.

따라서 오버라이딩해서 적어준다. left와 right, 맨 앞과 맨뒷값이다.

그리고 여기에서 mid값을 선언해준다.

왜냐면 반으로 나눠서 앞뒤,

왜냐면 반으로 나눠서 앞뒤,

왜냐면 반으로 나눠서 앞뒤, 왜냐면 반으로 나눠서 앞뒤, 왜냐면 반으로 나눠서 앞뒤,----------------------
를 해야하기 때문!

merge_sort(a, left, mid);

이 부분을 만나면 왼쪽을 계속 분할하게 될텐데 이걸 만나면 재귀로 돌아가서 

right에 mid값이 들어가서 다시 돌아돌아돌아돌아~~

한칸으로 나눠진다면 return문을 만나서 바로 직전에 두칸으로 간다.

여기서 스택에 저장되어있었던것들로 merge 함수가 실행!

---

 

public static void merge(int[] a, int left, int mid, int right) {
    int idx = left;
    int l = left;
    int r = mid + 1;
    while (l <= mid && r <= right) {
        if (a[l] <= a[r]) {
            sorted[idx] = a[l];
            l++;
            idx++;
        } else {
            sorted[idx] = a[r];
            r++;
            idx++;
        }
    }

    if (l > mid) {
        while(r<=right){
            sorted[idx] = a[r];
            idx++;
            r++;
        }
    } else{
        while (l <= mid) {
            sorted[idx] = a[l];
            idx++;
            l++;
        }
    }
    for (int i = left; i <= right; i++) {
        cnt++;
        a[i] = sorted[i];
        if (cnt == staticK) {
            System.out.println(a[i]);
            return;
        }
    }
}

이것이 바로 전설의 merge (병합) 매서드!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 

우선 idx를 선언해서 left를 넣어준다. idx는 sorted배열의 인덱스를 뜻한다.

left부터 넣어줘야하니까 left값을 넣어준 것이다.

l값과 r값이 각각 왼쪽 묶음, 오른쪽 묶음의 피붓이다.

이 피붓이 각각 mid, right에 도착하기 전까지 while문을 돌린다!

만약 a[l]값이 a[r]값보다 작다면!!!!!!!!!!!!!!

sorted배열에 a[l]값을 넣어줘서 정렬!해준다.

그러고나서 idx값과 l(또는 r)값을 ++해주는데, 만약 피붓이 기준점을 넘는다면 while문이 종료가 되고 if문으로 넘어간다.

while문이 넘었다는것은 둘 중 한 조건의 피붓이 기준점을 넘겼다는 뜻이고 이는 한쪽 배열이 다 비워졌다는 뜻이된다.

따라서 나머지 한쪽 배열을 고대ㅐㅐㅐㅐㅐㅐㅐㅐㅐ로 sorted에 넣어주면 된다.!

이제 정렬된 sorted배열을 원래의 배열 a에다가 넣어주면 된다.

a에 넣어주고 넣어주고 넣어주고 넣어주고 넣어주고 넣어주고 넣어주고 하면 촤라라라라라라라ㅏㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹㄹ라ㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏ하고 정렬이 될 것 이다.!

 

---

하지만 이 문제에서는 a배열에 K번째로 저장되는 놈에 대해서 출력해주는 것이므로 cnt==staticK 가 되는 시점에 print해주고 return 해주면 될 것이다.

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());
    staticK = Integer.parseInt(st.nextToken());
    int[] a = new int[N];
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++) {
        a[i] = Integer.parseInt(st.nextToken());
    }
    merge_sort(a);
    if (cnt < staticK) {
        System.out.println(-1);
    }

}

만약

cnt가 staticK보다 적게 시행이 된 경우가 있을 수 있으므로 그럴 경우에는 -1을 출력하게 해준다!

---

 

정말 오래 걸렸다. 그동안 블로그를 쓰지 못한 것은 내가 과연 공부를 소훌히 한 것일까 블로그를ㄹ 쓸 정도로 이해를 하지 못하고 넘어간 것들일까. 개강도 했겠다. 앞으로 더 열심히 해야겠따.

그럼! 안녕새우!!!!!!!!!!!!!!!!!!!!!!!!