백준 11004 k번째 수 구현 관련...

일단 cin, cout을 쓸 때, ios_base::sync_with_stdio(false); 를 써주지 않으면 시간초과를 받을 수 있다.

그리고 이전과 달리 STL sort를 사용해도 통과하느 것으로 보인다.

아무튼 quick sort를 응요한 quick selection을 이용해서 구현했는데...
맨 왼쪽 수를 pivot으로 정하고, pivot의 위치를 찾아내는 partition함수의 구현에서,

코드 1)-------------------------------------------------------------------------------------------
int partition(int left, int right) {
int pivot = left;
int lo = left + 1, hi = right;

while(lo < hi) {
while(arr[lo] <= arr[pivot] && lo <= right) lo++;

while(arr[hi] >= arr[pivot] && hi >= left + 1) hi--;

if(lo < hi) swapArr(lo, hi);
}

swapArr(hi, pivot);

return hi;
}
---------------------------------------------------------------------------------------------------
위의 코드와 같이 구현했다가, 틀렸는데 ,

아래 코드 2) 와 같이 구현하면

코드 2)-------------------------------------------------------------------------------------------
int partition(int left, int right) {
int pivot = left;
int lo = left + 1, hi = right;

while(lo <= hi) {
while(arr[lo] <= arr[pivot] && lo <= right) lo++;

while(arr[hi] >= arr[pivot] && hi >= left + 1) hi--;

if(lo < hi) swapArr(lo, hi);
}

swapArr(hi, pivot);

return hi;
}
---------------------------------------------------------------------------------------------------
맞았습니다를 받을 수 있다.

달라진 점은 while(lo < hi)  -> while(lo <= hi) 이다. 사실 처음에는 lo 와 hi가 같아질 일도 없고, 설령 같아지더라도 그 때 while문을 나오는 것이 문제될 일은 없다고 생각했다. 그런데 잘 생각해보니 길이가 2인 수열이 있으면 lo와 hi가 2로 같아져 아예 while문 안으로 들어갈 수 없게되는 문제가 있다.

그렇게 되면 예를 들어 {1, 2}라는 수열이 있을 때 hi값은 2가되어 while문 안에 못 들어가고, swapArr(hi, pivot)을 거쳐 {2, 1}로 수열을 변경하게 되어 잚못된 답이 나오게 된다.