백준 11582(치킨 TOP N) C언어

문제

11582번: 치킨 TOP N

간단한 머지소트 응용문제입니다. 그러다가 중간에 조건이 주어지고 그 조건에 들어가면 머지 소트를 멈추고

그대로 출력하는 문제입니다.

코드를 보겠습니다.

int arr[1048577];
int tmp[1048577];
int n;
int k;
int main(){
   scanf("%d",&n);
   for(int i=0;i<n;i++){
      scanf("%d",arr[i]);
   }
   
   scanf("%d",&k);
   merge_sort(arr,0,n-1);
   
   for (int i = 0; i < n; i++) {
		printf("%d ",arr[i]);
	}
    return 0;
}

정렬해야할 수가 2^20까지 이므로 배열의 크기를 2^20+1 까지 잡습니다.

배열과 변수 n, 변수 k를 전역변수로 설정한 이유는 머지소트를 함수로 구현하기 위함입니다.

main함수에서는 n을 입력받고, 정렬해야할 arr배열의 값을 입력받고 병합해야할 사람의 숫자인 k를 입력받습니다.

그다음 merge_sort 함수를 실행하고 마지막으로 정렬된 arr배열의 값을 출력시킵니다.

---

merge_sort부분입니다.

void merge_sort(int arr[], int l, int r) {
	if (l < r) {
		int m = (l + r) / 2;
		merge_sort(arr, l, m);
		merge_sort(arr, m + 1, r);
		merge(arr, l, m, r);
	}
}

일반 머지소트 방식과 유사합니다. 넘어가겠습니다.

---

merge부분입니다.

void merge(int arr[], int l, int m, int r) {
	if (r-l>n/k)
		return;
	int idx1, idx2, idx3;
	idx1= idx3 = l;
	idx2 = m + 1;
	while (idx1 <= m && idx2 <= r) {
		if (arr[idx1] < arr[idx2])
			tmp[idx3++] = arr[idx1++];
		else {
			tmp[idx3++] = arr[idx2++];
		}
	}
	if (idx1 == m + 1) {
		for (int i = idx2; i <= r; i++) {
			tmp[idx3++] = arr[i];
		}
	}
	else {
		for (int i = idx1; i <= m; i++) {
			tmp[idx3++] = arr[i];
		}
	}
	for (int i = l; i <= r; i++) {
		arr[i] = tmp[i];
	}
}

merge부분도 일반 merge부분과 매우 유사합니다. 하지만 if(r - l >n/k) return;  여기서 제일 중요한 코드입니다.

n / k부분은 1사람당 병합해야할 배열의 크기를 의미합니다. 또한 merge 함수 내에서 r - l 은 병합해야할 배열의

크기입니다.

예를 들어 n이 8이고 k가 2면 1사람당 병합해야할 배열의 크기가 4이고 만약 병합해야할 배열의 크기가 4보다 크면

2의 거듭제곱으로 배열의 크기가 8인 배열을 병합해야하므로 이는 k가 1일 때 가능합니다.

나머지는 일반 merge함수와 똑같습니다.

---

전체 코드입니다.

#include<stdio.h>
void merge_sort(int arr[], int l, int r);
void merge(int arr[], int l, int m, int r);
int n;
int k;
int arr[1048577];
int tmp[1048577];
int main() {
	scanf("%d",&n);
	for (int i = 0; i < n; i++) {
		scanf("%d",&arr[i]);
	}
	scanf("%d",&k);
	merge_sort(arr, 0, n - 1);
	for (int i = 0; i < n; i++) {
		printf("%d ",arr[i]);
	}
	return 0;
}
void merge_sort(int arr[], int l, int r) {
	if (l < r) {
		int m = (l + r) / 2;
		merge_sort(arr, l, m);
		merge_sort(arr, m + 1, r);
		merge(arr, l, m, r);
	}
}
void merge(int arr[], int l, int m, int r) {
	if (r-l>n/k)
		return;
	int idx1, idx2, idx3;
	idx1= idx3 = l;
	idx2 = m + 1;
	while (idx1 <= m && idx2 <= r) {
		if (arr[idx1] < arr[idx2])
			tmp[idx3++] = arr[idx1++];
		else {
			tmp[idx3++] = arr[idx2++];
		}
	}
	if (idx1 == m + 1) {
		for (int i = idx2; i <= r; i++) {
			tmp[idx3++] = arr[i];
		}
	}
	else {
		for (int i = idx1; i <= m; i++) {
			tmp[idx3++] = arr[i];
		}
	}
	for (int i = l; i <= r; i++) {
		arr[i] = tmp[i];
	}
}