백준 11582번: 치킨 TOP N (C++)

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

11582번: 치킨 TOP N

 

풀이

분할 정복 문제, 합병 정렬 알고리즘의 중간부분을 출력하는 문제.

알고리즘 수업때 수도코드 보고 구현했던 적이 있는데 막상 해보라니까 못해서 찾아봤다. 개어렵네 진짜 ㅡㅡ

 

내가 한 건 없고 그냥 코드 열심히 분석하면서 이해함..ㅜ

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, k;
vector<int> arr;
vector<int> arr2;

void merge(int left, int right){
	if ((right - left) > (N / k)) return;

	int mid = (left + right) / 2;

	int i = left; //왼쪽 값들의 인덱스
	int j = mid + 1; //오른쪽 값들의 인덱스
	int k = left; //arr2의 인덱스

	while (i <= mid && j <= right) {//합병과정
		if (arr[i] <= arr[j]) arr2[k++] = arr[i++];
		else arr2[k++] = arr[j++];
	}

	int tmp = i > mid ? j : i;
	while (k <= right) arr2[k++] = arr[tmp++]; //작은 값들 정렬 후 나머지 합병

	for (int i = left; i <= right; i++) arr[i] = arr2[i]; //원래 정렬에 복사
}

void partition(int left, int right){
	if (left < right){
		int mid = (left + right) / 2;
		partition(left, mid);
		partition(mid + 1, right);
		merge(left, right);
	}
}

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

	cin >> N;

	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		arr.push_back(a);
	}
	arr2.resize(N);
	
	cin >> k;

	partition(0, N - 1);

	for (int i = 0; i < N; i++) cout << arr2[i] << ' ';
}

 

 

참고 - https://dpdpwl.tistory.com/53