[C++] BOJ 11582번 : 치킨 TOP N

시간제한	메모리제한	알고리즘 분류
5 초	256 MB	정렬, 분할 정복

 

문제

인하대 주변 치킨칩의 맛의 정도를 측정해 수치화하는 동아리 C.T.P(Chicken Tastes Perfect)의 회장 민호는 치킨집의 맛의 수치를 감소하지 않는 순으로 정렬을 하고 싶었다. 하지만 치킨집이 너무 많아 혼자 정렬을 하기에는 많은 시간이 걸려 C.T.P 회원들을 활용하기로 했다. 치킨집이 N개 있다고 가정을 하자. N개의 치킨의 수치를 무작위로 놓은 뒤 N/2명의 C.T.P 회원이 차례대로 2개의 치킨집을 선택해  정렬을 한다. 그 뒤 N/4명이 차례대로 바로 전 단계의 사람이 정렬한 두 개의 그룹을 차례대로 선택 하여 치킨집을 정렬을 한다. 계속해서 N/8명, N/16명이 정렬을 진행하다가 마지막 사람이 두 개의 정렬된 그룹을 합병하여 작업을 완료한다.
예를 들어 8개의 치킨집의 점수가 (1, 5, 2, 4, 2, 9, 7, 3)과 같을 때, 첫 번째로 4명의 회원이(1, 5), (2, 4), (2, 9), (7, 3)을 각각 정렬하게 되면 (1, 5), (2, 4), (2, 9), (3, 7)이 되고, 두 번째로 2명의 회원이 ((1, 5), (2, 4))와 ((2, 9), (3, 7))을 정렬하면 (1, 2, 4, 5), (2, 3, 7, 9)가 되고, 최종적으로 1명의 회원이 ((1, 2, 4, 5), (2, 3, 7, 9))을 정렬하여 (1, 2, 2, 3, 4, 5, 7, 9)을 만들게 된다.
작업을 진행하던 중 문득 민호는 작업의 중간단계가 궁금해졌다. 현재 단계에서 k명의 회원이 정렬을 진행할 때 정렬을 마친 뒤 결과를 출력해라.

입력

첫 번째 줄에 치킨집의 개수 N(4 ≤ N ≤ 220)이 주어진다. N은 항상 2의 거듭제곱 꼴이다.
두 번째 줄에는 N개의 치킨집의 맛의 수치들이 빈칸을 구분으로 주어지며 이 값은 10억보다 작거나 같은 자연수 또는 0이다.
세 번째 줄에는 현재 정렬을 진행중인 회원들의 수 k(1 ≤ k < N)가 주어진다. k 또한 2의 거듭제곱 꼴이다.

출력

현재 단계에서 k명이 정렬을 진행한다고 할 때, 현재 단계가 완료한 상태를 출력하라.

제한 조건

1. N의 범위는 4 ≤ N ≤ 2^20 이다.
2. 맛의 수치(input)의 범위는 10억보다 작거나 같은 자연수 또는 0
3. 회원 수 K의 범위는 1 ≤ K ≤ N

예제 입력

8
1 5 2 4 2 9 7 3
2

예제 출력

1 2 4 5 2 3 7 9

---

문제 해결 조건

문제가 설명하는 정렬 방법은 무작위의 수의 중간을 나누고 정렬하고 또 나누고 정렬하는 합병 정렬(Merge sort) 방식이다. 다만, 작업의 중간 단계이자, 분할 횟수인 회원들의 수를 통해, 정렬 도중의 모습을 출력해야한다. 이 점에 주의해서 프로그램을 설계하자. int형은 2^32 까지 표현가능하므로 int로 n, input, k를 받으면 된다. 

 

프로그램 1차 설계

1. 합병 정렬을 수행하기 위한 횟수 level은 log n 이다. element의 수가 n개이므로, 시간복잡도는 O(nlogn).
2. k명이 정렬을 진행할 때, 각각의 회원이 정렬한 left array와 right array의 element 수는 n/k이다. 예를들어, 8개의 원소를 2명의 회원이 정렬했다면 각각 회원이 정렬한 배열은 4개의 원소를 갖고 있다.
3. k명의 회원이 현재 단계를 완료한 상태는 함수의 리턴 조건을 배열이 나뉘어있는 상태를 토대로 생각해보자. 2번의 예시처럼, 배열의 n/k만큼 정렬이 끝났으면 바로 함수를 종료시키면 되니까, merge 함수의 종료 조건을 (end - start) > (n/k)로 작성한다.

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

using namespace std;

int n, k;

/* 
i: 분할 후 왼쪽 리스트
j: 분할 후 오른쪽 리스트
w: 복사할 배열의 인덱스
*/

void merge(vector<int>& v, const int start, const int mid, const int end)
{	
	if (end - start> n / k)  return;
	int i = start;
	int j = mid + 1; //분할한 지점 +1의 인덱스
	int w = start; //시작 지점
	vector<int> sorted(v.size());

	//작은 순서대로 삽입
	while (i <= mid && j <= end) // 중간점과 배열의 끝 전에 닿기까지 진행
	{
		if (v[i] <= v[j]) {
			sorted[w++] = v[i++];
		}
		else { // a[i] > a[j]
			sorted[w++] = v[j++];
		}
	}
	if (i > mid)
	{
		copy(v.begin() + j, v.begin() + (end + 1), sorted.begin() + w);
	}
	else if (j > end)
	{
		copy(v.begin() + i, v.begin() + (mid + 1), sorted.begin() + w);
	}
	//임시리스트를 원래 리스트에 복사
	for (int t = start; t <= end; t++) v[t] = sorted[t];
}

void mergeSort(vector<int>& v, const int start, const int end) {
	if (start == end) return;
	if (start < end)
	{
		int mid = (start + end) / 2;
		mergeSort(v, start, mid);
		mergeSort(v, mid + 1, end);
		merge(v, start, mid, end);
	}
}


int main() {
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	cin >> k; //회원수
	mergeSort(v, 0, v.size() - 1);
	for (const auto& e:v) //벡터 v의 element를 반복자를 쓴 것처럼 호출..
	{
		cout << e << " ";
	}
}

1차 시도의 문제점

1차 시도는 유튜브 나동빈님의 merge sort tutorial 영상을 보고 arr로 작성한 코드를 벡터로 치환하며 작성해보았다. 그러나 메모리 사이즈에 대한 개념 이해가 부족한 탓인지 컴파일 시 vector subscript out of range 오류가 난다.. 계속해서 다른 자료들을 참고해 수정해보았지만 어디에서 문제가 생긴지 알기 어려워 처음부터 갈아 엎었다. 

 

2차 작성 코드

아래 코드는 주석과 함께 설명을 넣은 코드이다. 

분할 배열을 생성하는 경우 iterator인 i를 전위 증가 해야 벡터 컴파일 오류가 나지 않는다.

#include <iostream>
#include <vector>

using namespace std;
int n, input, k;

//merges two subvyas of vay[]. 원본 배열의 분할 배열을 병합한다.
void merge(vector<int>& v, int start, int mid, int end) {
	if (end - start > n / k) return;
	//분할 배열 생성
	vector<int> left(mid - start + 1);
	vector<int> right(end - mid);

	for (int i = 0; i < left.size(); ++i)
	{
		left[i] = v[start + i];
	}
	for (int i = 0; i < right.size(); ++i)
	{
		right[i] = v[mid + 1 + i];
	}

	/* merge two temporary vays	*/

	int i = 0, j = 0, w = start;

	while (i < left.size() && j < right.size()) {
		if (left[i] <= right[j])
		{
			v[w] = left[i];
			i++;
		}
		else {
			v[w] = right[j];
			j++;
		}
		w++;
	}

	//copy remainings
	while (i < left.size()) v[w++] = left[i++];
	while (j < right.size()) v[w++] = right[j++];
}

//main merge sort for v[start...end] using merge function
void mergeSort(vector<int>& v, int start, int end)
{
	if (start < end) // element num > 1;
	{
		int mid = (start + end) / 2;
		mergeSort(v, start, mid); //sort first half
		mergeSort(v, mid + 1, end); //sort second half
		merge(v, start, mid, end);
	}
}

int main() {
	cin >> n;
	vector<int>v(n);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	cin >> k;
	mergeSort(v, 0, v.size() - 1);
	for (const auto& e:v) {
		cout << e << " ";
	}
}

 

 

 

참고 링크

https://big-o.io/examples/merge-sort/c++/

http://www.cplusplus.com/reference/algorithm/merge/