백준 24051: 알고리즘 수업-병합 정렬1

[ 문제위치 ]

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

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

 

[ 문제풀이 ]

병합 정렬을 이용하여 배열을 정렬하는 것을 기본으로 하는 문제이다.

 

병합 정렬 알고리즘은 아래 링크에서 확인할 수 있다.

https://unlock546.tistory.com/7

병합 정렬

 

위 링크에 나와있는 의사코드를 통해 구현한 다음 특정 조건에서 조건문이 발생하도록 해당 변수를 만들어 카운드 해주면 된다.

 

#include <iostream>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

void merge_sort(int* A, int start, int end, int K);
void merge(int* A, int p, int q, int r, int K);
int cnt = 0;

int main(){
    fastio;
    int N, K;
    cin >> N >> K;
    int* A;
    A = new int[N];
    for(int i=0; i<N; i++)
        cin >> A[i];
    merge_sort(A,0,N-1,K);
    if(cnt<K) cout << -1;//예외처리
    return 0;
}

void merge_sort(int* A, int start, int end, int K){
    int p = start, r = end, q;
    if(p<r){
        q = (p+r)/2;
        merge_sort(A,p,q,K);
        merge_sort(A,q+1,r,K);
        merge(A,p,q,r,K);
    }
}

void merge(int* A, int p, int q, int r, int K){
    int *tmp;//크기를 받아서 사용하므로 포인터 선언
    tmp=(int*)malloc(sizeof(int)*(r+2));//malloc를 크기 배정
    int i = p, j = q+1, t = 1;
    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 = 1;
    while(i<=r){
        A[i++] = tmp[t++];
        if(++cnt==K)   cout << tmp[t-1];
    }
    free(tmp);
}