백준 11004번: K번째 수 (C++, 실버5)

문제

수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.
둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109)

 

 

출력

A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.

 

 

 

실패 코드

실패 이유: 시간 초과 

- vector를 사용하여 동적할당하던 것에서 전역변수로 바꿔 배열을 선언했는데도 시간 초과가 뜸.

- Quick Selection Sort라는 것을 이용하여 필요한 부분만 Sorting을 하고 있는데도 시간 초과가 뜸.

- cin, cout 등 입출력 속도를 향상시킬 수 있도록 명령어를 추가했는데 시간 초과가 뜸.

- Do It 책 볼 수밖에...

#include <iostream>
#include <vector>
using namespace std;

int n, k;
int nums[5000001];

void Swap(int arr[], int i, int j)
{
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

int Partition(int arr[], int start, int end)
{
	if (start + 1 == end)
	{
		if (arr[start] > arr[end])
			Swap(arr, start, end);
		return end;
	}
	int middle = (start + end) / 2;
	Swap(arr, middle, start);
	int pivot = start;
	int i = start + 1, j = end;
	while (i <= j)
	{
		while (i <= end && arr[i] <= arr[pivot]) i++;
		while (j > start && arr[j] >= arr[pivot]) j--;
		if (i <= j)
		{
			Swap(arr, i, j);
			i++, j--;
		}
		else break;
	}
	Swap(arr, pivot, j);
	return j;
}

void QuickSort(int arr[], int start, int end)
{
	if (start >= end)
		return;

	int pivot = Partition(arr, start, end);
	if (pivot == k)
		return;
	if (k < pivot)
		QuickSort(arr, start, pivot - 1);
	else
		QuickSort(arr, pivot + 1, end);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> k;
	k -= 1;
	for (int i = 0; i < n; i++)
		cin >> nums[i];

	QuickSort(nums, 0, n - 1);

	cout << nums[k];
}

 

 

 

성공 코드

35-37줄 코드가 중요하다. 처음에 pivot을 swap 했다는 것을 잊고 따로 위치 지정을 안 했는데, 이 코드가 핵심이었다.

이 코드를 추가하니까 성공했다.

휴............. 제발..............

진짜..................

살려줘.......................

#include <iostream>
#include <vector>
using namespace std;

int n, k;
int nums[5000001];

void Swap(int arr[], int i, int j)
{
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

int Partition(int arr[], int start, int end)
{
	if (start + 1 == end)
	{
		if (arr[start] > arr[end])
			Swap(arr, start, end);
		return end;
	}
	int middle = (start + end) / 2;
	Swap(arr, middle, start);
	int pivot = arr[start];
	int i = start + 1, j = end;
	while (i <= j)
	{
		while (j >= start + 1 && arr[j] > pivot) j--;
		while (i <= end && arr[i] < pivot) i++;
		if (i < j)
			Swap(arr, i++, j--);
		else break;
	}
	arr[start] = arr[j];
	arr[j] = pivot;
	return j;
}

void QuickSort(int arr[], int start, int end)
{
	int pivot = Partition(arr, start, end);
	if (pivot == k)
		return;
	if (k < pivot)
		QuickSort(arr, start, pivot - 1);
	else
		QuickSort(arr, pivot + 1, end);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> k;
	k -= 1;
	for (int i = 0; i < n; i++)
		cin >> nums[i];

	QuickSort(nums, 0, n - 1);

	cout << nums[k];
}