프로그래밍 문제풀이 도움좀 주실분!!!

[ㅂㅇㅈㅂㅇ(121.135)]

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

여기서 저는

입력 을 전부 받고나서

퀵소트로 정렬하고 K번째 인덱스 접근해서 찾았더니

시간 초과 뜨네요 ..

어떤 방법이 있을까요???

[합격(143.248)]

사이즈가 K인 배열 만들어서 숫자 들어올 때마다 그 배열의 max 값이랑 비교하는 식으로 하면 되겠네. max보다 크면 버리고 max보다 작으면 집어넣고, max값 변동되면 바꿔주고. 집어넣을 때는 binary insertion sort 하는 식으로 하는게 제일 빠를 듯. 근데 K가 N이랑 거의 비슷하다든지 하는 최악의 케이스에는 어차피 똑같이 오래걸릴 것 같다.

[합격(143.248)]

K가 N에 가까운지 1에 가까운지 판별해서 오름차순으로 할지 내림차순으로 할지 결정하면 시간 좀 더 절약 가능하겠네. 그렇게 하면 K가 N/2 에 가까울 때가 최악의 케이스가 됨.

[wefwef(121.135)]

으 그래도 아직 잘 안되네요 ㅜㅜ 답변 감사합니다!