BOJ 11004 - K번째 수

17 Mar 2017 on Algorithm

출처 BOJ

K번째 수

문제

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

입력

첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.
둘째에는 $A_{1}, A_{2}, A_{3}, ..., A_{N}$ 이 주어진다. ( $-10^{9} \le A \le 10^{9}$ )

출력

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

예제

범위체크

$-10^{9} \le A \le 10^{9} \le INT$

풀이

모두 정렬하고 k번째 값을 구하는 것은 너무 오래걸리고 비효율적
→ k번째만 정렬 되면 됨(quick sort 사용)

코드

quick sort 사용code

#include<cstdio>
#include<algorithm>
#define BOUND 5000001
using namespace std;

int N,K;
int A[BOUND];

void search(int start, int end){
	int idx = start;
	int val = A[end-1];
	for(int i=start; i<end-1; i++){
		if(A[i] < val){
			swap(A[idx],A[i]);
			idx++;
		}
	}
	swap(A[idx],A[end-1]);

	if(K==idx)
		printf("%d\n",A[K]);
	else if(K <idx)
		search(start,idx);
	else
		search(idx+1,end);
}	

int main(){
	scanf("%d%d",&N,&K);
	K = K-1;
	for(int i=0; i<N; i++)
		scanf("%d",&A[i]);
	
	search(0,N);
}

c++의 nth_element 사용code

#include<cstdio>
#include<algorithm>
#define BOUND 5000001
using namespace std;

int N,K;
int A[BOUND];

int main(){
	scanf("%d%d",&N,&K);
	K = K-1;
	for(int i=0; i<N; i++)
		scanf("%d",&A[i]);

	nth_element(A,A+K,A+N);
	
	printf("%d\n",A[K]);	
}

복잡도

$T(n) = T({n \over 2}) + n$ : k번째기준 좌,우 둘중 한 방향으로만 탐색하기 때문에
$\le T({n \over {2^{k}}}) + kn = T(1) + kn (2^{k} = n$ → $k = logn)$
→ $O(NlogN)$