[백준] 24060번 : 알고리즘 수업 - 병합 정렬 1 _ JAVA ( 주석 설명 )

1번

→ 병합 정렬 코드를 이해하고, K번째 저장되는 수를 출력하는 문제

 

어떻게 재귀 함수가 호출되고 실행되는지 정확히 이해하는데 아래 자료들의 도움을 받았다.

---

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

 

https://reakwon.tistory.com/38

[알고리즘] 병합 정렬 (Merge Sort) 기본 개념과 코드 구현, 설명

---

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

public class Main {
    static int[] sorted; //정렬 배열을 저장할 임시 공간
    static int count = 0; //저장 횟수를 카운팅하기 위한 변수
    static int K; //저장횟수 변수, merge 함수에서 count == K 로 쓰인다.
    static int result = -1; //N번째 저장되는 수를 담는 변수, default : -1

    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()); //배열의 크기를 입력받는다.
        K = Integer.parseInt(st.nextToken()); //저장 횟수를 입력받는다.

        int[] ary = new int[N]; //N만큼의 배열을 생성한다.
        sorted = new int[N];

        st = new StringTokenizer(br.readLine()); //다음 개행이므로 새로 정의해준다.
        for(int i=0;i<N;++i){
            int num = Integer.parseInt(st.nextToken());
            ary[i] = num; //서로 다른 배열 원소들을 저장해준다.
        }

        merge_sort(ary, 0 , N-1); //ary 배열을 merge_sort 한다.

        System.out.println(result);
    }


    //분할
    //재귀적 호출 => 끝없이 분할하고, 정렬된 형태로 정복한다.
    private static void merge_sort(int[] ary, int left, int right) {
        if(left<right){
            int mid = (left+right)/2;

            merge_sort(ary, left,mid); //중앙을 기준으로 왼쪽 분할 정렬
            merge_sort(ary, mid+1,right); //오른쪽 분할 정렬
            merge(ary,left,mid,right); //왼쪽 오른쪽 분할 리스트 병합
        }
    }


    private static void merge(int[] ary, int left, int mid, int right) {
        int i = left; //분할 정렬의 왼쪽 리스트에 대한 인덱스
        int j = mid+1; //분할 정렬의 오른쪽 리스트에 대한 인덱스
        int k = 0; //정렬 리스트에 대한 인덱스

        //분할 정렬된 List 합병
        while(i<=mid && j<=right) { //왼쪽 or 오른쪽 리스트 중 한 쪽 리스트 비교가 다 끝날 때까지
            if (ary[i] < ary[j]) {
                sorted[k++] = ary[i++];
            } else
                sorted[k++] = ary[j++];
        }

        while(i<=mid){ //왼쪽 리스트가 남았을 경우
            sorted[k++] = ary[i++];
        }

        while(j<=right){ //오른쪽 리스트가 남았을 경우
            sorted[k++] = ary[j++];
        }

        k = 0;
        for(int l=left;l<=right;++l){ //배열 sorted[](임시 배열)의 리스트를 배열 ary[]로 재복사
            count++; //저장횟수를 카운팅한다.
            if(count==K){ //저장횟수가 입력된 수와 같으면 저장되는 수를 파악하고 break를 한다.
                result = sorted[k];
                break;
            }
            ary[l] = sorted[k++];
        }
    }
}