문제 번호 24060번 : 병합 정렬 1 - JAVA [자바]

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

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

문제 설명

 

재귀를 사용한 병합 정렬에서 정렬되는 순서에 따른 값을 출력하는 문제입니다.

 

문제 풀이

문제에서는 병합정렬 로직이 풀이로 나와있지만 해당 언어를 알지 못하거나 병합정렬 알고리즘에 대한 이해가 없으면 풀기가 쉽지 않습니다. 병합 정렬에 대한 내용은 다음 게시물에 올려놓았습니다. 

병합정렬이 관하여

자바로 구현한 합병 정렬(병합 정렬) 알고리즘 - 분할 정복

 

정답 코드

import java.util.Scanner;

public class Main {

    static int num = 1;
    static boolean flag = true;
    static int[] sort_array;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int array_length = sc.nextInt();
        int print_num = sc.nextInt();

        int[] array = new int[array_length];
        sort_array = new int[array_length];

        for(int i=0; i<array.length; i++){
            array[i] = sc.nextInt();
        }

        merge_sort(array,0,array_length-1,print_num);

        if(flag == true){
            System.out.println(-1);
        }

//        for(int i=0; i<array.length; i++){
//            System.out.printf("%d ",array[i]);
//        }
    }

    public static void merge_sort(int[] array, int first, int second,int print_num){



        if(first == second) return;

        int mid = (first+second)/2;

        merge_sort(array,first,mid,print_num);
        merge_sort(array,mid+1,second,print_num);

        merge(array,first,mid,second,print_num);

    }

    public static void merge(int[] array, int first, int mid, int second,int print_num){
        int l = first;
        int m = mid+1;
        int index = first;

        while(l<=mid && m<=second){
            if(array[l] <= array[m]){
                sort_array[index] = array[l];
                if(num == print_num){
                    System.out.println(sort_array[index]);
                    flag = false;
                }
                num++;
                l++;
                index++;
            }
            else{
                sort_array[index] = array[m];
                if(num == print_num){
                    System.out.println(sort_array[index]);
                    flag = false;
                }
                num++;
                m++;
                index++;
            }
        }

        while(l<=mid){
            sort_array[index] = array[l];
            if(num == print_num){
                System.out.println(sort_array[index]);
                flag = false;
            }
            num++;
            l++;
            index++;
        }
        while(m<=second){
            sort_array[index] = array[m];
            if(num == print_num){
                System.out.println(sort_array[index]);
                flag = false;
            }
            num++;
            m++;
            index++;
        }

        for(int i=first; i<=second; i++){
            array[i] = sort_array[i];
        }




    }

}

해당 숫자가 변경 될때마다 list를 하나씩 올려주고 flag값으로 출력이 되지 않았을 경우 -1을 출력합니다.

병합정렬 알고리즘을 구현할 수 있다면 어려운 문제는 아닙니다.