게임 개발 로그

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

코테

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

03:00am 2024. 12. 12. 15:18

문제

수 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];
}