백준 24060

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

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

 

<문제 요약>

병합정렬할 배열이 주어지면 K번째 저장되는 숫자를 출력하는 것!

 병합 정렬은 

https://www.youtube.com/watch?v=ctkuGoJPmAE&pp=ygUM67OR7ZWp7KCV66Cs

여기서 잘 설명해주신다 ..

대충 

8개 배열이 있으면

           4 4  

    2 2         2 2 

1 1  1 1  1 1  1 1

이런 식으로 나눠서 위로 올라가며 정렬한다 .

 

시간복잡도는 n*logn 최악에서도 동일하다.

 

 

<풀이 코드>

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

public class P24060 {


    static int[] tmp;
    static int K;
    static int result=-1;
    static int cnt;


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

        StringTokenizer arrSt = new StringTokenizer(br.readLine());
        int[] mergeArr = new int[N];
        tmp=new int[N];

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

        mergesort(mergeArr,0,mergeArr.length-1);
        System.out.println(result);

    }

    static void mergesort(int[] arr,int first,int last){
        if(first<last){
            int mid=(first+last)/2;
            mergesort(arr,first,mid);
            mergesort(arr,mid+1,last);
            merge(arr,first,mid,last);
        }
    }

    static void merge(int[] arr,int first,int mid,int last){
        int i=first;
        int j=mid+1;
        int index=0;
        while(i<=mid && j<=last){
            if(arr[i]<=arr[j]) tmp[index++]=arr[i++];
            else tmp[index++]=arr[j++];
        }

        while(i<=mid){
            tmp[index++] =arr[i++];
        }
        while (j<=last){
            tmp[index++]=arr[j++];
        }

        index=0;
        i=first;

        while(i<= last){
            cnt++;
            if(cnt==K) {
                result=tmp[index];
                break;}
            arr[i++]=tmp[index++];
        }

    }

}

 

문제에 의사코드가 있으니 잘보고 구현하면 된다.

물론 나는 제대로 구현 못해서 다른 블로그들 참고했다 ..