Level 1 K번째 수

시간 복잡도: O(T * n lgn), T = 테스트 케이스 (commands)

1#include <bits/stdc++.h>
2
3using namespace std;
4
5vector<int> solution(vector<int> array, vector<vector<int>> commands) {
6    vector<int> answer;
7    for(int i=0; i<commands.size(); ++i) {
8        vector<int> c = commands[i];
9        vector<int> temp;
10        for(int i=c[0]; i<=c[1]; ++i) temp.push_back(array[i-1]);
11        sort(temp.begin(), temp.end());
12        answer.push_back(temp[c[2]-1]);
13    }
14    return answer;
15}

원래는 sort() 에서 시작점과 끝을 지정해서 구간만 정렬 한 다음 거기서 바로 k번째를 구할려고 했는데 문법이 생각이 안나서 위처럼 풀었다. 그리고 다른 사람의 풀이를 보았는데,,, 이거였다.

1for(int i = 0; i < commands.size(); i++) {
2    temp = array;
3    sort(temp.begin() + commands[i][0] - 1, temp.begin() + commands[i][1]);
4    answer.push_back(temp[commands[i][0] + commands[i][2]-2]);
5}