본문 바로가기

Computer Science&Engineering/코딩테스트

[백준 11004] K번째 수

# 문제링크

www.acmicpc.net/problem/11004

 

11004번: K번째 수

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

www.acmicpc.net

정렬해서 K 번째 있는 수를 구해야 한다. C++의 STL에 sort 를 활용해서 배열을 완전히 정렬한 후 K번째 값을 출력하면 된다. 

 

정렬해서 몇 번째에 있는 수를 알려주는 STL인 nth_element 함수가 있다. 

nth_element(시작, 찾고자하는 인덱스, 끝) 이렇게 넣어주면 된다. 

 

# 제출 코드 

 

// sort 를 이용한 풀이

 

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

 

// nth_element 를 이용한 풀이

 

#include <cstdio>
#include <algorithm>
using namespace std;
long long int a[5000001];
int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	k -= 1;
	for (int i = 0; i < n; i++) {
		scanf("%lld", &a[i]);
	}
	nth_element(a, a + k, a + n);
	printf("%lld", a[k]);
	return 0;
}

 

둘이 시간 차이는 크게 나지 않는다.

 

반응형