-
[PS] 백준 16455번: K번째 수 찾는 함수문제해결 2023. 11. 1. 20:55
Reafy 수열 이 문제를 풀어보려고 이것저것 찾다가 16455번까지 오게되었다.
결국 저건 카운팅 소트로 했지만...
quick selection이라는 알고리즘이 존재한다더라.
이를 이용해서 빠른 시간 이내에 k번째 수를 찾는게 정답.
quick selection을 대충 조사해보니 일종의 이진탐색과 비슷해보이는데
우선 아무거나 하나를 골라서,
그 수보다 작은건 왼쪽, 큰건 오른쪽에 몰아넣으며 탐색공간을 줄여나가는 것이다.
위 그림의 4번, 5번 과정
if (pivval < a[lidx] && a[ridx] < pivval) { swap(a[lidx], a[ridx]); lidx++, ridx--; }
코드로는 위 부분에서
조건을
if (pivval <= a[lidx] && a[ridx] <= pivval) { swap(a[lidx], a[ridx]); lidx++, ridx--; }
이렇게 잡으니 계속 TLE가 떴다.
자기자신끼리 swap 하느라 쓸데없이 시간을 정말 많이 썼나보더라.
1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... 1 1 1 1 1 1 1 1 1 1 1 1 이런 테케가 있으면 확실히 swap한다고 실행시간이 최소 3배가 되지 않았을까 싶다.
#include <bits/stdc++.h> using namespace std; int repartition(vector<int> &a, int lidx, int ridx) { int pividx = lidx + rand() % (ridx - lidx + 1); swap(a[pividx], a[ridx]); int pivval = a[ridx]; pividx = ridx; ridx -= 1; while (lidx <= ridx) { if (pivval < a[lidx] && a[ridx] < pivval) { swap(a[lidx], a[ridx]); lidx++, ridx--; } else { if (a[lidx] <= pivval) lidx += 1; if (pivval <= a[ridx]) ridx -= 1; } } swap(a[lidx], a[pividx]); return lidx; } int quick_select(vector<int> &a, int k, int lidx, int ridx) { while (lidx <= ridx) { int pividx = repartition(a, lidx, ridx); if (pividx < k) { lidx = pividx + 1; } else if (k < pividx) { ridx = pividx - 1; } else return a[pividx]; } return -1; } int kth(vector<int> &a, int k) { return quick_select(a, k - 1, 0, a.size() - 1);; }
'문제해결' 카테고리의 다른 글
[PS] 백준 1882번: 분수 찾기, 30449번: Reafy 수열 (0) 2023.11.07 [PS] 백준 13908번: 비밀번호 (1) 2023.11.02 [PS] 백준 30446번: 회문수 (2) 2023.10.28 [PS] 백준 2749번: 피보나치 수 3 / 11444번: 피보나치 수 6 (0) 2023.10.26 [PS] 백준 1748번: 수 이어 쓰기1 (0) 2023.10.25