[코딩테스트] [프로그래머스] K번째 수

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42748

---

풀이

1. 일정 범위 내의 부분 배열을 저장하기 위해 새 벡터를 만들어 push_back 하고, 이를 algorithm 헤더의 sort 함수를 사용해서 정렬하니까 시간 초과 문제가 발생하였음

2. 루트가 최대인 우선순위 큐 사용하여 O(logN)의 시간에 정렬되도록 하여서 해결함

---

코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) 
{
    vector<int> answer;
    
    for (int i=0; i<commands.size(); i++)
    {
        int start = commands[i][0];
        int end = commands[i][1];
        int size = commands[i][2];
        
        --start;
        --end;
        
        priority_queue<int, vector<int>, greater<int>> sub;
        for(int j=start; j<=end; j++)
        {
            sub.push(array[j]);
        }
        
        while(size > 1)
        {
            sub.pop();
            --size;
        }
        
        answer.push_back(sub.top());
    }
    
    return answer;
}