<백준> 11004번 K번쨰 수

문제

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

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

문제 해결 과정:

-벡터 안에 차레대로 숫자를 넣고

-sort로 정렬 후 K번째 출력

- 시간 초과 뜸,, N이 5,000,000까지 이므로 이것을 정렬 하는 과정에서 1.5초를 넘는것 같은데

- c++ stl에서 sort는 quick sort로 시간 복잡도가 O(nlogn)인데 이것보다 더 효율적인 것이 있을까?

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
 
int main() {
    int N;
    int K;
    int temp;
    scanf_s("%d %d", &N, &K);
 
    vector<int> a;
    for (int i = 0; i < N; i++) {
        cin >> temp;
        a.push_back(temp);
    }
 
    sort(a.begin(), a.end());
 
    cout << a[K - 1] << endl;
 
    return 0;
}

-추가: 

-여러가지 방법을 해보다가 cout과 cin을 scanf와 printf로 바꾸었더니 1432ms로 시간초과에 걸리지 않아싿.

-인터넷에 찾아보니 scanf와 printf는 변수타입을 지정해 주기 때문에 속도가 좀 더 빠르지만 안전하지 않음

-벡터를 사용하는 것보다 배열을 동적할당하여 사용하는 것이 메모리와 시간을 덜 잡아 먹음

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
 
int main() {
    int N;
    int K;
 
    scanf_s("%d %d", &N, &K);
     
    int *a = new int[N];
    for (int i = 0; i < N; i++) {
        scanf_s("%d",&a[i]);
    }
 
    sort(&a[0],&a[N]);
 
    printf("%d", a[K - 1]);
 
    return 0;
}