[백준/BOJ] 1026. 보물 [Silver 4]

1026. 보물

문제 출처 : https://www.acmicpc.net/problem/1026

문제에 낚시가 있는데, B에 있는 수는 재배열하지 말라고 했는데, 채점방식에 B배열을 검사하는것이 아니기 때문에, B를 오름차순하던 내림차순을하던 채점할때는 알길이 없기때문에 정렬해도 된다. 사실 정렬안하면 할수야 있겠지만 하기 싫을것이다.... 정렬을 해야 원활하게 풀리는 문제임

그래서 퀵소트로 정렬을 했는데, 계속 시간초과가 나는것이다....

code1

#include <stdio.h>
void QuickSort(int* arr, int start, int end)
{
	if (start >= end)
		return;
	int piv = start, left = start + 1, right = end, temp;
	while (left < right)
	{
		while (left <= end && arr[left] <= arr[piv])
			left++;
		while (right > start && arr[right] >= arr[piv])
			right--;
		if (left > right)
		{
			temp = arr[right];
			arr[right] = arr[piv];
			arr[piv] = temp;
		}
		else
		{
			temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
		}
	}
	QuickSort(arr, start, right - 1);
	QuickSort(arr, right + 1, end);
}
void QuickSort1(int* arr, int start, int end)
{
	if (start >= end)
		return;
	int piv = start, left = start + 1, right = end, temp;
	while (left < right)
	{
		while (left <= end && arr[left] > arr[piv])
			left++;
		while (right > start && arr[right] < arr[piv])
			right--;
		if (left > right)
		{
			temp = arr[right];
			arr[right] = arr[piv];
			arr[piv] = temp;
		}
		else
		{
			temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
		}
	}
	QuickSort1(arr, start, right - 1);
	QuickSort1(arr, right + 1, end);
}
int main()
{
	int N, i, A[50] = { 0 }, B[50] = { 0 }, S = 0;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
		scanf("%d", &A[i]);
	for (i = 0; i < N; i++)
		scanf("%d", &B[i]);
	QuickSort(A, 0, N - 1);
	QuickSort1(B, 0, N - 1);
	for (i = 0; i < N; i++)
		S += A[i] * B[i];
	printf("%d", S);
	return 0;
}

그래서 어차피 N의 갯수가 50개정도 밖에안되기 때문에 시간복잡도상으로 버블소트나 퀵소트가 그렇게 차이가 안날것이라 판단해서 (버블소트가 코드길이도 짧긴하다.) 버블소트를 써봤더니 시간초과문제가 해결되었다.

code2

#include <stdio.h>
void BubbleSort(int arr[], int num)
{
	int i, j, temp;
	for (i = num - 1; i > 0; i--)
		for (j = 0; j < i; j++)
			if (arr[j] > arr[j + 1])
			{
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
}
int main()
{
	int N, i, A[50] = { 0 }, B[50] = { 0 }, S = 0;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
		scanf("%d", &A[i]);
	for (i = 0; i < N; i++)
		scanf("%d", &B[i]);
	BubbleSort(A, N);
	BubbleSort(B, N);
	int j = N - 1;
	for (i = 0; i < N; i++)
	{
		S += A[i] * B[j];
		j--;
	}
	printf("%d", S);
	return 0;
}