[정렬] 백준 11004 :: K번째 수

K번째 수 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	20846	6412	3559	37.938%

문제

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

입력

첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.

둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109)

출력

A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.

예제 입력 1 

5 2
4 1 2 3 5

예제 출력 1 

2

가 

 문제 풀이

1차 풀이 ( 40932 KB,  1132 ms)

• std::sort()로 정렬 한 뒤, K번째 요소 출력.
• stdio와의 동기화 해제.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
        //! 입출력 속도 향상
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int32_t N, Kth;
        cin >> N >> Kth;
        int64_t arr[N];
        for(int32_t i=0; i<N; i++){
                cin >> arr[i];
        }
        sort(arr, arr+N);
        cout << arr[Kth-1];
}

2차 풀이 ( 40928 KB,  796 ms)

• std::sort() 대신,  std::nth_element() 사용.
• stdio와의 동기화 해제.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
        //! 입출력 속도 향상
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int32_t N, Kth;
        cin >> N >> Kth;
        int64_t arr[N];
        for(int32_t i=0; i<N; i++){
                cin >> arr[i];
        }
        nth_element(arr, arr+Kth-1, arr+N);
        cout << arr[Kth-1];
}

3차 풀이 ( 41952 KB,  148 ms)

• std::nth_element() 사용.
• 저수준 입출력 사용.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int BUF_SIZE = 1 << 20;
char buf[BUF_SIZE];
int p;

inline char _read_char()
{
        if (p == BUF_SIZE)
        {
                fread(buf, sizeof(char), BUF_SIZE, stdin);
                p = 0;
        }
        return buf[p++];
}
inline int64_t readInt()
{
        bool negative = false;
        int32_t tmp;
        int64_t ret = 0;
        while (true)
        {
                tmp = _read_char();
                if(tmp == '-' ) {
                        negative = true;
                        continue;
                }
                if(tmp == '\n') break;
                if(tmp == ' ' ) break;
                ret = ret * 10 + (tmp & 0b1111);
        }
        return negative ? -ret : ret;
}



int main() {
        //! 입출력 속도 향상
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int64_t N, Kth;
        N = readInt();
        Kth = readInt();

        int64_t arr[N];
        for(int64_t i=0; i<N; i++){
                arr[i] = readInt();
        }
        nth_element(arr, arr+Kth-1, arr+N);
        cout << arr[Kth-1];
}

 추가 노트,

직접 구현한 nth_element()를 사용했더니, 시간 초과에 걸렸다.

피벗을 맨 뒤의 요소로 했을 때, 20% 수준에서 시간초과가 났으므로,

정렬된 케이스가 있는 것 같다.

피벗을 랜덤으로 정했을 때, 92% 수준에서 시간초과가 났으므로,

직접 구현한 nth_element()가 대용량에서는 버티지 못한다는 것을 알 수 있다.

왠만하면 std 에서 제공하는 표준 라이브러리를 사용하자,..