[BOJ/백준/C++] 24060번 알고리즘 수업 - 병합 정렬 1

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

---

반응형

📌 접근 방법

• 합병정렬을 이용하여 풀었다.

 

✔ 합병정렬(Merge Sort)

출처 : 위키백과

• 배열이 2 개의 배열로 분할되고 크기가 1/2로 감소하는 분할 정복 알고리즘
  
  • 크기가 n인 배열을 n/2 크기의 2개의 배열로 분할하는 것을 반복
  • 더이상 분할할 수 없을 때 오름차순으로 다시 정렬하며 합병하는 것 !
• 성능 : nlogn

 

✅  Pass Code

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iterator>
#include<map>
#include<set>
#include<unordered_set>
#include <stack>
#include<queue>
#include<deque>

using namespace std;
int cnt=0,K,result=-1;
void mergeSort(int p, int r, int *arr){
    if(p>=r)return ;
    int q=(p+r)/2;
    mergeSort(p,q,arr);
    mergeSort(q+1,r,arr);
    int i=p,j=q+1,k=1;
    int tmp[r];
    while(i<=q&&j<=r){
        if(arr[i]<=arr[j]){
            tmp[k++]=arr[i++];
        }
        else{
            tmp[k++]=arr[j++];
        }
    }
    while(i<=q){
        tmp[k++]=arr[i++];

    }
    while(j<=r)tmp[k++]=arr[j++];
    i=p,k=1;
    while(i<=r){
        arr[i]=tmp[k];
        cnt++;
        if(cnt==K)result=arr[i];
        i++,k++;
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin>>N>>K;
    int arr[N];
    for(int i=0; i<N; i++){
        cin>>arr[i];
    }
    mergeSort(0,N-1,arr);
    cout<<result;
    return 0;
}