[프로그래머스] [C++] K번째 수

문제 풀이

 

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

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    
    // 자동 정렬을 위한 우선순위 큐 생성. 오름차순으로 사용하기 위해 greater<int> 사용
    priority_queue<int, vector<int>, greater<int>> pq;
	
	for (int i = 0; i < commands.size(); i++) {
    	
        	// command[i][0]부터 command[i][1]까지 우선순위 큐에 넣는다. 
        	// j-1을 하는 이유는 배열의 인덱스가 0부터 시작하기 때문.
		for (int j = commands[i][0]; j <= commands[i][1]; j++) pq.push(array[j - 1]);
            
        	// .back()은 배열의 가장 마지막 원소를 뜻한다. 여기서는 K번째 수를 가리키는 숫자를 뜻한다.        
        	// k번째 수가 가장 앞으로 올 때까지 pop한다.
        	for (int m = 1; m < commands[i].back(); m++) pq.pop();
        
        	// 현재 pq에는 K번째 수가 가장 앞에 있으므로 가장 앞에 있는 수(pq.top())을 answer에 넣어준다.
		answer.push_back(pq.top());
        
        	// pq를 다시 쓰기 위해 pq를 비워준다.
		while (!pq.empty()) pq.pop();
	}
    return answer;
}

 

 

 

문제 링크

 

programmers.co.kr/learn/courses/30/lessons/42748?language=cpp

코딩테스트 연습 - K번째수