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

문제 : 24060

풀이 point

병합 정렬을 구현한 후 K번째로 저장되는 수를 출력하면 된다. 병합 정렬은 의사코드를 그대로 구현한다.

풀이 방법

의사코드를 구현한 후
A[i] = tmp[i](원본 배열에 붙여넣기 하는 과정)에서 cnt를 증가시키며 cnt가 K가 됐을 때 tmp[i-1]을 출력한다.

//백준 24060, 알고리즘 수업 - 병합 정렬 1
#include <iostream>

int A[500'001];
int tmp[500'001];
int cnt{0};
int N, K;
bool flag = false;

void merge(int p, int q, int r){

	int i = p; int j = q + 1; int 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++];
		++cnt;
		if(cnt == K){			
            std::cout << A[i - 1];
			flag = true;
			return;
		}
	}
}

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

int main(void){
	std::cin >> N >> K;

	for (int i = 0; i < N; i++) std::cin >> A[i];
	
	merge_sort(0, N-1);

	if(!flag) std::cout << -1;

	return 0;
}

사족

의사 코드대로 구현하지 않으면 정렬 순서가 어긋나기 때문에 의사 코드대로 구현해야한다.