게임 개발 로그
백준 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]; }
'코테' 카테고리의 다른 글
백준 2751: 수 정렬하기 2(C++, 실버5) (1) | 2024.12.12 |
---|---|
백준 11399번: ATM (C++, 실버3) (0) | 2024.12.11 |
4일차 / 홀짝에 따라 다른 값 반환하기 / C++ / 기초 (2) | 2023.11.03 |
3일차 / 더 크게 합치기 / C++ / 기초 (0) | 2023.11.02 |
3일차 / 문자 리스트를 문자열로 변환하기 / C++ / 기초 (0) | 2023.11.02 |