[11004번] K번째 수(Quick Search)

문제 출처 :

 

https://www.acmicpc.net/problem/11004

알고리즘 분석 :

문제 해결에 필요한 사항

1. k번째 수를 찾아 내는 방법

2. 시간초과를 면하는 방법

퀵 정렬의 응용 버전인 퀵 서치(Quick Search)를 이용하여 빠른 시간내에 원하는 값을 찾아 내는 방법이다.

아래 주소는 퀵 서치에 대한 내용들을 담아두고 있다.

http://createcode.tistory.com/entry/%EC%A0%95%EB%A0%AC%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Quick-Sort-%ED%80%B5%EC%86%8C%ED%8A%B8

http://hackability.kr/entry/Quick-Selection%EC%9D%84-%EC%9D%B4%EC%9A%A9%ED%95%9C-On-%EC%84%A0%ED%83%9D-%EB%B0%A9%EB%B2%95

소스 코드 : 

#include <stdio.h>
 
int arr[5000001];
 
void Swap(int arr[], int a, int b) // a,b 스왑 함수 
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
 
int Partition(int arr[], int left, int right)
{
    int pivot = arr[left]; // 피벗의 위치는 가장 왼쪽에서 시작
    int low = left + 1;
    int high = right;
 
 
    while (low <= high) // 교차되기 전까지 반복한다 
    {
        while (pivot >= arr[low] && low <= right) // 피벗보다 큰 값을 찾는 과정 
        {
            low++; // low를 오른쪽으로 이동 
        }
 
        while (pivot <= arr[high] && high >= (left + 1)) // 피벗보다 작은 값을 찾는 과정 
        {
            high--; // high를 왼쪽으로 이동
        }
 
        if (low <= high)// 교차되지 않은 상태이면 스왑 과정 실행 
        {
            Swap(arr, low, high); //low와 high를 스왑 
        }
 
    }
    Swap(arr, left, high); // 피벗과 high가 가리키는 대상을 교환 
    return high;  // 옮겨진 피벗의 위치정보를 반환 
 
}
 
 
int QuickSearch(int arr[], int left, int right, int k)
{
    int pivot = Partition(arr, left, right); // 둘로 나누어서
    if (pivot == k)
        return arr[pivot];
 
    else if (pivot > k)
        QuickSearch(arr, left, pivot - 1, k); // 왼쪽 영역을 정렬한다.
 
    else
        QuickSearch(arr, pivot + 1, right, k); // 오른쪽 영역을 정렬한다.
}
 
 
 
int main()
{
    int n, k, i;
    int cnt = 0;
 
    scanf("%d %d", &n, &k);
    k--;
 
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    printf("%d", QuickSearch(arr, 0, n - 1, k));
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>