[BaekJoon][7469] K번째 숫자

BAEKJOON ONLINE JUDGE

7469 K번째 숫자

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

O(n*m) 이하로 풀어야 하는 문제

처음에 quick select로 문제를 풀려 하였으나

O(m*n + a)라서 시간초과

O(n*m) -> 입력을 index와 값을 같이 저장한 후

   값을 기준으로 정렬

   정렬한 값을 다 돌면서 index가 주어진 범위안에 있는 수 중 k 번째를 찾아서 출력

#include <cstdio>
#include <algorithm>
using namespace std;
 
struct Number {
    int num, idx;
};
 
int n;
Number num[100001];
 
bool cmp(const Number &first, const Number &second)
{
    return first.num < second.num;
}
 
int main()
{
    int m;
    int i, j;
    int s, e, k;
 
    scanf("%d %d", &n, &m);
 
    for (i = 1; i <= n; i++) {
        scanf("%d", &num[i].num);
        num[i].idx = i;
    }
 
    sort(num + 1, num + n + 1, cmp);
 
    for (i = 0; i < m; i++) {
        scanf("%d %d %d", &s, &e, &k);
 
        int cnt = 0;
        for (j = 1; j <= n; j++) {
            if (num[j].idx >= s && num[j].idx <= e)    cnt++;
            if (cnt == k)    {
                printf("%d\n", num[j].num);
                break;    
            }
        }
    }
 
    return 0;
}