[P&B] #112 BAEKJOON 24060

백준 24060번 JAVA 알고리즘 수업 - 병합 정렬 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 ≤ 10^8)가 주어진다.

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

 

출력

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

 

나의 문제 풀이 코드

import java.util.*;

class MergeArray{
    int[] A;
    private int[] tmp;
    private int k;
    private int cnt;
    
    MergeArray(int n, int k){
        A = new int[n];
        tmp = new int[n];
        this.k = k;
        cnt = 0;
    }
    
    public void merge_sort(int p, int r) {		//배열 A를 클래스 멤버 변수로
        int q;
        if (p < r) {
            q = (p + r) / 2;
            merge_sort(p, q);
            merge_sort(q + 1, r);
            merge(p, q, r);
        }
    }

    private void merge(int p, int q, int r) {
        int i = p;
        int j = q + 1;
        int t = 0;				//배열은 0부터 시작하기에 0으로 초기화
        while (i <= q && j <= r) {
            if (A[i] <= A[j])
                tmp[t++] = A[i++];
            else
                tmp[t++] = A[j++];
        }
        while (i <= q)
            tmp[t++] = A[i++];
        while (j <= r)
            tmp[t++] = A[j++];
        i = p; t = 0;				//바로 위 주석과 같은 이유
        while (i <= r) {
            A[i++] = tmp[t++];
            cnt++;
            if(cnt == k) {
                System.out.println(A[i - 1]);
                System.exit(0);
            }
        }
    }
}

class bj24060{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        MergeArray m = new MergeArray(n, k);
        for(int i = 0; i < n; i++)
            m.A[i] = sc.nextInt();
        m.merge_sort(0, n - 1);				//배열은 0부터 n-1까지이기 때문에
        System.out.println(-1);
        sc.close();
    }
}

 

문제 풀이 코멘트

문제 풀이에 앞서 병합 병렬에 대해 알아보았습니다.

병합 정렬(Merge Sort)은 배열을 분할하고 정복(divide and conquer) 알고리즘을 기반으로하는 정렬 알고리즘입니다. 배열을 두 개의 부분 배열로 나누고, 각 부분 배열을 정렬한 다음 병합하여 더 큰 배열을 생성하는 방식으로 동작합니다. 이렇게 반복하면서 전체 배열이 정렬됩니다.

1. 분할(Divide): 주어진 배열을 중간 지점에서 두 개의 하위 배열로 분할합니다. 이때 중간 지점을 계산하는 방법은 (p + r) / 2로 구할 수 있으며, 여기서 p는 부분 배열의 시작 인덱스이고 r은 끝 인덱스입니다.
2. 정복(Conquer): 각 하위 배열에 대해 재귀적으로 병합 정렬을 호출합니다. 이렇게 하위 배열은 계속해서 더 작은 부분 배열로 분할하고 정렬합니다.
3. 병합(Merge): 두 정렬된 하위 배열을 병합합니다. 이때 두 개의 포인터(i와 j)를 사용하여 두 배열을 비교하고, 더 작은 원소를 새로운 배열에 넣습니다. 이 과정을 반복하여 하위 배열을 병합합니다.

이러한 분할 및 병합 과정을 재귀적으로 반복하여 배열을 정렬합니다. 병합 정렬은 안정적인 정렬 알고리즘으로, 최악의 경우에도 O(n log n)의 시간 복잡도를 가집니다. 또한, 병합 정렬은 추가적인 배열(일반적으로 tmp 배열)을 사용하여 데이터를 임시로 저장하므로, 메모리 사용량이 더 많을 수 있습니다.

병합 정렬의 주요 특징은 다음과 같습니다. 

• 안정적인 정렬 알고리즘
• 시간 복잡도가 평균과 최악의 경우에도 O(n log n)이므로 매우 효율적
• 추가 메모리를 사용하므로 메모리 효율성은 낮을 수 있으나, 빠른 속도로 정렬을 수행

 

문제에서 안내해 준 크기가 N인 배열에 대한 병합 정렬 의사 코드를 하나의 클래스 'MergeArray'로 구현했습니다.

• A: 정렬할 배열을 저장하기 위한 멤버 변수
• tmp: 병합 작업 중에 임시로 데이터를 저장하는 배열
• k: 상위 k개 원소를 찾기 위한 변수
• cnt: 현재 찾은 원소의 개수를 저장하는 변수

위의 변수들을 정의해 준 다음 병합 정렬 의사 코드를 자바 형으로 정리하여 메서드로 생성해주었습니다.

 

MergeArray 생성자는 n과 k를 입력받아 n크기의 배열 A와 임시 배열 tmp를 초기화하고 클래스 내 k 초기화및 cnt를 설정하는 생성자입니다.

 

 merge_sort(int p, int r) 메서드는 배열 A를 정렬하는 메서드로, 주어진 범위 p부터 r까지를 정렬합니다.
배열을 반으로 나누고 각 반을 재귀적으로 정렬한 다음 merge 메서드를 사용하여 두 개의 정렬된 하위 배열을 병합합니다.

 

 merge(int p, int q, int r) 메서드는 두 개의 정렬된 배열을 병합하는 메서드로, p부터 q까지와 q+1부터 r까지의 두 하위 배열을 병합합니다. i와 j는 각각 첫 번째 배열과 두 번째 배열의 인덱스를 나타내며, t는 임시 배열 tmp의 인덱스를 나타냅니다.

 while 루프를 사용하여 두 배열을 비교하고 더 작은 원소를 tmp에 저장한 다음 해당 배열의 인덱스를 증가시킵니다. 이후에는 남은 원소를 복사하여 정렬된 배열 A에 저장하며, cnt를 증가시킵니다. 만약 cnt가 k와 같다면, k번째로 큰 원소를 찾은 것으로 간주하고 해당 값을 출력한 후 프로그램을 종료합니다.

 

코드의 주요 목적은 배열을 병합 정렬하여 정렬된 결과를 얻는 것이지만, 중간에 cnt를 사용하여 상위 k개의 원소를 추적하고 출력하며, 그 중에서도 k번째 원소를 찾으면 프로그램을 종료하는 부분이 특별한 기능입니다.