[백준] 2217번 문제풀이

문제 : www.acmicpc.net/problem/2217

 

알고리즘 :

1. N개를 입력 받음.

2. Merge Sort로 정렬 (오름차순)

3. 정렬된 값 x index의 MAX를 구함.

4. Max출력

 

Merge Sort 구현 후, Over Flow가 발생하여서 원인을 분석해보니, merge 함수 내부에서 100,000개의 배열을 선언하다 보니 그런 것 같았다. 그래서 내부 temp배열을 전역 변수로 선언하니, 문제없이 동작하였다.

확실히 빠르긴 하지만, 저장공간이 필요하다는 단점이 있다.

 

첫 번째 코드는, MAX를 Merge Sort를 이용해서 구하는 것이고,

두 번째 코드는, MAX를 for문을 이용해서 구하는 것이다.

 

첫 번째 코드는 Merge Sort를 이용하지만, for문으로 배열에 넣어주는 작업이 있었기 때문에,

시간 복잡도는 O(n)+O(n log(n))이다. n이 100,000일 때 150,000번 수행하였다.

 

두 번째 코드는 For문을 이용하여서 시간 복잡도는 O(n)이다. 100,000번 수행하였다.

(아주 귀여운 친구가 도움을 주었다!)

 

첫 번째 코드는 32ms, 두 번째 코드는 24ms가 나왔다.

 

코드 1 :

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#define MAX 100000

void mergeSort(int* arr, int left, int right);
void merge(int* arr, int left, int mid, int right);

int temp[MAX];

int main(void)
{
	int w[MAX];
	int rope[MAX];
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf(" %d", &w[i]);
	}

	mergeSort(w, 0, n - 1);

	for (int i = 0; i < n; i++)
	{
		rope[i] = w[i] * (n - i);
	}

	mergeSort(rope, 0, n - 1);
	
	printf("%d ", rope[n - 1]);
	return 0;
}

void mergeSort(int* arr, int left, int right)
{
	if (left == right) { return; }
	int mid = (left + right) / 2;
	mergeSort(arr, left, mid);
	mergeSort(arr, mid + 1, right);
	merge(arr, left, mid, right);
}

void merge(int* arr, int left, int mid, int right)
{
	int i = left;
	int j = mid + 1;
	int k = left;

	while (i <= mid && j <= right)
	{
		if (arr[i] < arr[j])
		{
			temp[k++] = arr[i++];
		}
		else
		{
			temp[k++] = arr[j++];
		}
	}
	while (i <= mid) { temp[k++] = arr[i++]; }
	while (j <= right) { temp[k++] = arr[j++]; }
	for (int a = left; a <= right; a++)
	{
		arr[a] = temp[a];
	}

	return;
}

 

코드 2:

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#define MAX 100000

void mergeSort(int* arr, int left, int right);
void merge(int* arr, int left, int mid, int right);

int temp[MAX];

int main(void)
{
	int w[MAX];
	int rope[MAX];
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf(" %d", &w[i]);
	}

	mergeSort(w, 0, n - 1);

	int max = 0;

	for (int i = 0; i < n; i++)
	{
		rope[i] = w[i] * (n - i);
		if (rope[i] > max) max = rope[i];
	}
	
	printf("%d ", max);
	return 0;
}

void mergeSort(int* arr, int left, int right)
{
	if (left == right) { return; }
	int mid = (left + right) / 2;
	mergeSort(arr, left, mid);
	mergeSort(arr, mid + 1, right);
	merge(arr, left, mid, right);
}

void merge(int* arr, int left, int mid, int right)
{
	int i = left;
	int j = mid + 1;
	int k = left;

	while (i <= mid && j <= right)
	{
		if (arr[i] < arr[j])
		{
			temp[k++] = arr[i++];
		}
		else
		{
			temp[k++] = arr[j++];
		}
	}
	while (i <= mid) { temp[k++] = arr[i++]; }
	while (j <= right) { temp[k++] = arr[j++]; }
	for (int a = left; a <= right; a++)
	{
		arr[a] = temp[a];
	}

	return;
}

 

걸린 시간 : 72분 (37분 알고리즘, 35분 구현 및 디버깅)

가장 인상적인 시간 배분이었던 것 같다.

구현을 정확하게 하니까 디버깅 시간이 엄청나게 줄었다.

코드를 빠르게 짜는 것 보다도 천천히 꼼꼼히 짜면서 체크해나가는 게 더 중요한 것 같다.

 

테스트케이스 : 

2
10
15

2
15
15

3
13
10
15

4
10
20
30
40

4
40
30
20
10

5
13
46
27
58
40

6
100
1
2
3
4
5

7
5
7
9
15
14
10
6