[JAVA] 백준 24060 - 알고리즘 수업- 병합 정렬 1

실버III

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

24060번: 알고리즘 수업 - 병합 정렬 1

문제

오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자.

크기가 N인 배열에 대한 병합 정렬 의사 코드는 다음과 같다.

merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다.
    if (p < r) then {
        q <- ⌊(p + r) / 2⌋;       # q는 p, r의 중간 지점
        merge_sort(A, p, q);      # 전반부 정렬
        merge_sort(A, q + 1, r);  # 후반부 정렬
        merge(A, p, q, r);        # 병합
    }
}

# A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
# A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
merge(A[], p, q, r) {
    i <- p; j <- q + 1; t <- 1;
    while (i ≤ q and j ≤ r) {
        if (A[i] ≤ A[j])
        then tmp[t++] <- A[i++]; # tmp[t] <- A[i]; t++; i++;
        else tmp[t++] <- A[j++]; # tmp[t] <- A[j]; t++; j++;
    }
    while (i ≤ q)  # 왼쪽 배열 부분이 남은 경우
        tmp[t++] <- A[i++];
    while (j ≤ r)  # 오른쪽 배열 부분이 남은 경우
        tmp[t++] <- A[j++];
    i <- p; t <- 1;
    while (i ≤ r)  # 결과를 A[p..r]에 저장
        A[i++] <- tmp[t++]; 
}

---

입력

첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다.

다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

---

출력

배열 A에 K 번째 저장 되는 수를 출력한다. 저장 횟수가 K 보다 작으면 -1을 출력한다.

---

접근방법

[4] [5] [1] [3] [2] 배열의 요소를 예시로 설명을 해보자면,

 

1. 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.

전반부는 p부터 중간지점인 q까지이므로 [4], [5]까지, 후반부는 [1], [3], [2]가 된다.

그럼 재귀로 또 분할한다. 전반부는 [4]와 [5]로 분할되고, 후반부는 [1]과 [3], [2]로 분할된다.

 

2. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.

[4], [5]는 그대로, [1] 그대로, [3], [2]는 순서가 바뀌어 정복된다.

따라서, [4] [5] / [1] / [2] [3] 과 같이 정복된다.

 

3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다. 이 부분리스트들을 결합하여 오름차순 정렬형태로 만든다.

 

cnt를 전역변수로 두어 결과를 저장할 때마다 횟수를 들려주었고, cnt가 K와 같아지게 되면 그때 저장되는 요소를 result에 저장하였다.

---

코드

 

package 재귀;

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

public class SLIVER3_BJ24060 {
    /*https://www.acmicpc.net/problem/24060
    알고리즘 수업-병합정렬1
     */

    static int[] tmp;
    static int cnt = 0; //저장횟수
    static int K;
    static int result = 0;
    public static void main(String args[])throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        //N과 K입력
        int N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        //배열 A입력
        int[] A = new int[N];
        tmp = new int[N];

        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++)
            A[i] = Integer.parseInt(st.nextToken());

        merge_sort(A, 0, (N - 1));

        if(cnt < K)
            System.out.println(-1);
        else
            System.out.println(result);
    }

    public static void merge_sort(int A[], int p, int r) { // A[p..r]을 오름차순 정렬한다.
        if (p < r) {
            int q = (p + r) / 2;       // q는 p, r의 중간 지점
            merge_sort(A, p, q);      // 전반부 정렬
            merge_sort(A, q + 1, r);  // 후반부 정렬
            merge(A, p, q, r);        // 병합
        }
    }

    //A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
    //A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
    public static void merge(int A[], int p, int q, int r) {
        int i = p;
        int j = q + 1;
        int t = 0;

        while (i <= q && j <= r) {
            //왼쪽이 오른쪽보다 작으면 왼쪽 요소를 tmp에 저장
            if (A[i] <= A[j])
                tmp[t++] = A[i++];
            // 왼쪽이 오른쪽보다 작으면 오른쪽 요소를 tmp에 저장
            else
                tmp[t++] = A[j++];
        }

        while (i <= q) { // 왼쪽 배열 부분이 남은 경우
            tmp[t++] = A[i++];
        }
        while (j <= r) {  // 오른쪽 배열 부분이 남은 경우
            tmp[t++] = A[j++];
        }
        i = p;
        t = 0;
        // 결과를 A[p..r]에 저장
        while (i <= r){
            A[i] = tmp[t];
            //저장 후 저장횟수 증가
            cnt++;

            //K번째 저장횟수의 A[i]를 result에 저장
            if(K == cnt) {
                result = A[i];
            }
            i++;
            t++;
        }
    }
}

---

NOTE

코드는 완성하였지만 이해가 완벽하게 되지 않아 아래 블로그들을 참고하여 mergeSort에 대한 이해를 하려고 했다.

하지만 완벽하게 이해가 되지 않은 것 같아 위의 설명도 틀린 부분이 있을 수 있고 많이 부족하다.

좀 더 공부를 해야할 필요성을 느꼈다.

https://velog.io/@gogumi4502/Java-%EB%B0%B1%EC%A4%80-24060-%EC%9E%AC%EA%B7%80

[Java] 백준 #24060 (재귀)

https://dongdori.com/entry/Beginner%EB%B0%B1%EC%A4%80-24060%EB%B2%88-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%88%98%EC%97%85-%EB%B3%91%ED%95%A9-%EC%A0%95%EB%A0%AC-1

[Beginner][백준] 24060번 : 알고리즘 수업 - 병합 정렬 1