[BOJ11004][C++] K번째 수 : 오름차순 정렬

문제

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

 

 

입력

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

둘째에는 이 주어진다. ()

 

 

출력

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

 

 

예제 입력

5 2  4 1 2 3 5

 

예제 출력

2

 

 

힌트

 

 

출처

· 문제를 만든 사람: baekjoon

 

 

알고리즘 분류

· 정렬

 

 

코드

 

#include <cstdio>
#include <algorithm>
using namespace std;
int n, k, N[5000000];
int main()
{
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", N + i);                                                                     
    sort(N, N + n);
    printf("%d\n", N[k-1]);
    return 0;
}

---

- 버블정렬 방법의 시간 복잡도는 O(n²)이기 때문에 이 문제를 통과할 수 없다.

- 따라서 <algorithm> 헤더를 include하여 sort() 함수를 사용하였다. (sort() 함수의 시간 복잡도는 O(nlog₂n).)

- 또 최대한 실행 시간이 낭비되지 않도록 cin, cout 대신 scanf, printf를 사용하였고, scanf("%d", N + i); 를 사용하여 배열에 숫자가 대입되도록 하였다.

 (간혹 sort()를 사용해도 시간 제한을 넘기는 경우가 있다고 해서 신경을 써서 코드를 작성하였다.)