[백준/BOJ]16471. 작은 수 내기 [Silver 5]

16471. 작은 수 내기

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

code

#include <stdio.h>
void QuickSort(int *arr, int start, int end)
{
	if (start >= end)
		return;
	int piv = start;
	int 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);
}
int main()
{
	int N, i, cnt = 0;
	int Ju[100000] = { NULL }, Sa[100000] = { NULL };
	scanf("%d", &N);
	for (i = 0; i < N; i++)
		scanf("%d", &Ju[i]);
	for (i = 0; i < N; i++)
		scanf("%d", &Sa[i]);
	QuickSort(Ju, 0, N - 1);
	QuickSort(Sa, 0, N - 1);
	for (i = 0; i < N / 2 + 1; i++)
		if (Ju[i] < Sa[N / 2 + i])
			cnt++;
	if (cnt >= (N + 1) / 2)
		printf("YES");
	else
		printf("NO");
	return 0;
}

내가 비주얼 스튜디오로 짠 코드를보면 버블정렬, 삽입정렬, 선택정렬 다해봤는데, 백준에서 시간초과가 나버리는 바람에 시간복잡도가 가장 작은 퀵정렬로 하니까 되더라.