엘리스 코드 챌린지 Day 2 정리 정돈을 좋아하는 k씨

문제

 

풀이

주어진 배열에서 l ~ r의 범위를 골라서 오름차순으로 정렬하고 idx번째에 위치한 수를 구하는 문제입니다.

N = 10000, M = 500이므로 브루트포스를 사용하여 M * N * logN 시간으로 해결할 수 있습니다.

저는 l ~ r 범위의 수들을 벡터에 넣어줬고, 벡터를 오름차순으로 정렬하여 idx번째 수를 출력하는 방식으로 해결했습니다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 10001
using namespace std;
 
int list[MAX];
int N, M;
 
void func() {
    int l, r, idx;
    while (M--) {
        cin >> l >> r >> idx;
        vector<int> tmp;
        for (int i = l; i <= r; i++) {
            tmp.push_back(list[i]);
        }
        sort(tmp.begin(), tmp.end());
        cout << tmp[idx - 1] << '\n';
        tmp.clear();
    }
}
 
void input() {
    int x;
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}