[프로그래머스] [C++] 이중우선순위큐

문제 풀이

 

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

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    // 자동 정렬을 위한 우선순위 큐 생성. 우선순위 큐는 "내림차순"으로 정렬된다!
    priority_queue<int> pq;
	
    // operations를 돌면서
	for (int i = 0; i < operations.size(); i++) {
    	
        // 명렁어가 I 숫자라면
		if (operations[i][0] == 'I') {
        	
            // 공백 이후 숫자부분(substr(2))을 숫자로 바꾸어(stoi) 우선순위 큐에 저장
			pq.push(stoi(operations[i].substr(2)));
		}
		
        // 우선순위 큐에 값이 존재하는 경우
		if (!pq.empty()) {
        	
            // "D 1"은 최댓값 삭제 명령어이고 우선순위 큐는 내림차순이라 가장 앞이 최댓값이다. 
            // 때문에 그냥 pop을 해주면 끝.
			if (operations[i] == "D 1") {
				pq.pop();
			}
			
            // "D -1"은 최솟값 삭제 명령어이다. 때문에 우선순위 큐를 오름차순으로 바꿔줄 필요가 있다.
			else if (operations[i] == "D -1") {
            	
                // 오름차순 우선순위 큐를 생성. 
				priority_queue<int, vector<int>, greater<int>> g_pq;
                
                // 오름차순 큐에 원래 큐를 다 넣어준다.
				while (!pq.empty()) {
					g_pq.push(pq.top());
					pq.pop();
				}
                
                // 오름차순이 되어 가장 앞이 최솟값이 되었다. 이제 최솟값을 pop한 후
				g_pq.pop();
                
                // 다시 내림차순 큐에 집어넣어주도록 한다.
				while (!g_pq.empty()) {
					pq.push(g_pq.top());
					g_pq.pop();
				}
			}
		}
	}

	// pq 에 값이 존재한다면
	if (!pq.empty()) {
    	// 최대, 최솟값을 찾기 위한 임시배열 생성
		vector<int> tmp;
        
        // pq의 값을 tmp에 이전한 후
		while (!pq.empty()) {
			tmp.push_back(pq.top());
			pq.pop();
		}
        
        // 최대, 최솟값을 찾아 answer에 [최대, 최소]의 순으로 넣어준다.       
        // *max(min)_element(배열.begin(), 배열.end()); 은 해당 배열에서 최대, 최소값을 찾아주는 기능을 한다. <algorithm> 헤더에 있다.
        int maxval, minval;
		maxval = *max_element(tmp.begin(), tmp.end());
		minval = *min_element(tmp.begin(), tmp.end());
		answer.push_back(maxval);
		answer.push_back(minval);
	}
    
    // pq가 비어있다면 [0, 0]을 만들어준다.
	else {
		answer.push_back(0);
		answer.push_back(0);
	}
    
    return answer;
}

 

 

 

문제 링크

 

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

코딩테스트 연습 - 이중우선순위큐