본문 바로가기

# Foundation/백준풀이

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

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초512 MB208466412355937.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)


2차 풀이 ( 40928 KB,  796 ms)


3차 풀이 ( 41952 KB,  148 ms)


 추가 노트,

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


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

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


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

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


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