백준 11004 - k번째 수

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

11004번: K번째 수

문제 풀이

---

수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.

 

접근 방식

---

간단합니다 수를 정렬하고 해당 인덱스에 있는 수를 출력하면 됩니다. 이러한 문제들은 대표적으로 시가 복잡도를 계산하고 코드의 효율성을 판단하는 문제입니다. 3가지의 풀이 방식을 해보았습니다. (참고) 아래로 갈수록 더 좋은 효율성을 가지고 있습니다.

 

코드

---

[Algorithm 라이브러리 sort 함수 사용]

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n,k;
vector<int>v;
int main(void){
	//아래의 입출력 효율성을 높여주는 장치를 반드시 작성해야 순조롭게 작동 됩니다.
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>k;
    for(int i=0;i<n;i++){
        int temp;cin>>temp;
        v.push_back(temp);
    }
    sort(v.begin(),v.end());
    cout<<v[k-1]<<"\n";
    return 0;
}

[Quick Sort 사용]

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n,cnt, quick[5000001],k;
void quickSort(int i, int j)
{
    if(i>=j) return;

    int pivot = quick[(i+j)/2];
    int left = i;
    int right = j;
    while(left<=right){
        while(quick[left]<pivot) left++;
        while(quick[right]>pivot) right--;
        if(left<=right){
            swap(quick[left],quick[right]);
            left++; right--;
        }
    }
    quickSort(i,right);
    quickSort(left,j);
}
int main() 
{
    scanf("%d %d",&n,&k);
    for(int i = 0; i < n; i++) scanf("%d",&quick[i]);
    quickSort(0,n-1);
    printf("%d\n",quick[k-1]);
}

[Quick selection 사용 (Algorithm 라이브러리 제공)]

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n,k;
vector<int>v;
int main(void){
	//아래의 입출력 효율성을 높여주는 장치를 반드시 작성해야 순조롭게 작동 됩니다.
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>k;
    for(int i=0;i<n;i++){
        int temp;cin>>temp;
        v.push_back(temp);
    }
    nth_element(v.begin(),v.begin()+(k-1),v.end());
    cout<<v[k-1]<<"\n";
    return 0;
}

순서대로 sort, Quick sort , Quick Selection 입니다.

funny algorithm *0*b ~