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

문제링크

• 백준 24060

문제설명

• 병합정렬로 배열 A를 오름차순 정렬할 때, 병합 단계에서 K번째로 저장되는 정렬된 원소를 찾아라.
• 즉, 각 단계에서 비교연산 후 배열에 새롭게 저장될 때 K번째로 저장되는 원소를 찾는 것이다.

문제접근방향(bokyoung)

• 병합정렬을 재귀호출을 이용하여 구현한다.
• 병합 단계에서 원소의 위치가 정해질 때마다 저장 횟수를 1씩 올린다.
• 저장횟수가 K가 될때, 해당 원소값을 기록해둔다.
• K보다 저장횟수가 작은 경우가 있을 수 있으므로 원소값을 기록해두는 변수의 초기값은 -1로 설정한다.
• 정렬이 완료되면 K번째 저장된 원소를 출력한다.

구현

#include <iostream>
#include <vector>
using namespace std;

int N, K;
int cnt = 0;
int ans = -1;

// A[p...q]와 A[q+1...r]을 병합하여 A[p...r]을 오름차순 정렬된 상태로 만든다.
void merge(vector<int>& A, int p, int q, int r)
{
	int i = p, j = q + 1, t = 0;
	vector<int> tmp;
	while (i <= q && j <= r) {
		if (A[i] < A[j])
			tmp.push_back(A[i++]);
		else
			tmp.push_back(A[j++]);
		cnt++;
		if (cnt == K) // K번째 저장된 수
			ans = tmp.back();
	}

	// 왼쪽 배열 부분이 남은 경우
	while (i <= q) {
		tmp.push_back(A[i++]);
		cnt++;
		if (cnt == K) // K번째 저장된 수
			ans = tmp.back();
	}
	// 오른쪽 배열 부분이 남은 경우
	while (j <= r) {
		tmp.push_back(A[j++]);
		cnt++;
		if (cnt == K) // K번째 저장된 수
			ans = tmp.back();
	}

	// 결과를 배열 A에 저장
	i = p;
	while (i <= r)
		A[i++] = tmp[t++];
}

// p는 분할된 배열의 좌측 끝, r은 우측 끝을 나타낸다.
void merge_sort(vector<int>& A, int p, int r)
{
	if (p < r) {
		int q = (p + r) / 2; // 중간 지점을 찾는다.
		merge_sort(A, p, q); // 전반부 정렬
		merge_sort(A, q + 1, r); // 후반부 정렬
		merge(A, p, q, r); // 병합
	}
}

int main(void)
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> N >> K;
	vector<int> A(N);
	for (int i = 0; i < N; i++)
		cin >> A[i];
	merge_sort(A, 0, N-1);
	cout << ans << endl;

	return 0;
}