문제 출처

단계별로 풀어보기 > 재귀 > 알고리즘 수업 - 병합 정렬 1
https://www.acmicpc.net/problem/24060

문제 설명

배열 A의 크기 N, 저장 횟수 K가 주어질 때, 병합 정렬시에 K번째 저장되는 수를 출력하라

접근 방법

병합 정렬시에 임시로 정렬된 배열 tmp를 원래 배열로 옮길 때 하나씩 옮긴다.
이 때 하나씩 옮길 때, 순서가 진행되기에 count를 증가시킨다.
해당 count가 k가 되었을 때 결과를 출력한다.

import java.io.*;
import java.util.*;

public class 알고리즘_수업_병합_정렬_1 {
    static int[] A, tmp;
    static int N, K, count = 0, result = -1;

    public static void mergeSort(int start, int end) {
        if (start < end) {
            int mid = (start + end) / 2;
            mergeSort(start, mid);
            mergeSort(mid + 1, end);
            merge(start, mid, end);
        }
    }

    public static void merge(int start, int mid, int end) {
        int i = start, j = mid + 1, t = start;

        while (i <= mid && j <= end) {
            if (A[i] <= A[j]) {
                tmp[t++] = A[i++];
            } else {
                tmp[t++] = A[j++];
            }
        }

        while (i <= mid) {
            tmp[t++] = A[i++];
        }

        while (j <= end) {
            tmp[t++] = A[j++];
        }

        for (int idx = start; idx <= end; idx++) {
            A[idx] = tmp[idx];
            count++;
            if (count == K) {
                result = A[idx];
                return;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        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());
        }

        mergeSort(0, N - 1);
        System.out.println(result);
    }
}

Review

import java.io.*;
import java.util.StringTokenizer;

public class 알고리즘_수업_병합_정렬_1_review {

    public static int A[];
    static int tmp[];
    public static int count = 0;
    public static int end = 0;
    public static int result = -1;

    public static void merge_sort(int p, int r){
        if (p < r){
            int q = (p + r) /2;
            merge_sort(p,q);
            merge_sort(q+1,r);
            merge(p,q,r);
        }
    }

    public static void merge(int p, int q, int r){
        int i = p;
        int j = q+1;
        int t = p;



        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++];
        }

        for(int idx = p; idx <= r; idx++){
            A[idx] = tmp[idx];
            count++;
            if (count == end){
                result = A[idx];
                return;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        A = new int[N];
        tmp = new int[N];

        int K = Integer.parseInt(st.nextToken());

        end = K;

        st = new StringTokenizer(br.readLine());

        for(int i = 0; i<N; i++){
            A[i] = Integer.parseInt(st.nextToken());
        }

        merge_sort(0,N-1);

        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
        br.close();


    }

}

알게된 점

병합 정렬 코드의 경우 문제에서 주어졌지만, 가장 중요한 부분은 정렬되는 순서를 어떻게 저장하는가가 문제 풀이가 가장 중요한 부분인 것 같다.

문제푼 흔적

Review