[백준 7469] k번째 수

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

7469번: K번째 수

요구사항

주어진 범위에서의 k번째 수를 구하여라

 

풀이

start~end까지 새로운 배열으로 입력 받아 정렬 후, 거기에서 k번째 수를 출력하니 시간초과이다

최대값으로 들어온다 했을때 정렬 하는데 O(Nlogn)을 소비하기 때문이다

 

start ~ end 까지 중 k번째 수를 구하는 문제니깐

본 배열에 idx를 포함시켜 정렬 후, start~end에 포함 되어있다면 cnt++을 해주고 cnt==k일때가 정답이다

https://jaimemin.tistory.com/744

를 참조하였다...어려웡

 

#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;
struct go {
	ll x;
	int y;

};
int n, m;
bool com(go a, go b) {
	if (a.x < b.x) return true;
	return false;
}
go map[100100];
void q(int start, int end, int want) {
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (map[i].y >= start && map[i].y <= end) {
			cnt++;
		}
		if (cnt == want) {
			printf("%lld\n", map[i].x);
			return;
		}
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%lld", &map[i].x);
		map[i].y = i + 1;
	}
	sort(map, map + n, com);

	for (int i = 0; i < m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		q(x, y, z);
	}
}