프로그래머스(Programmers) 알고리즘 문제풀이 - 이중우선순위큐

Taesun Lee·2020년 7월 23일
0

algorithm-study

목록 보기
2/10

이중우선순위큐

프로그래머스에서 힙 카테고리의 '이중우선순위큐' 문제를 풀어보았다.
문제링크

기억할 내용

앞, 뒤 모두에서 pop, push가 되는 deque

deque를 이용하면 push_back(), push_front(), pop_front(), pop_back()을 사용해서 앞, 뒤 모두에서 자유자제로 push, pop 할 수 있다.

substr을 이용한 string 자르기

substr를 이용하면 string을 자를 수 있는데, 인자를 하나면 주면, 해당 index부터 끝까지의 string을 얻어 올 수 있다. 만약 두번째 인사를 사용할 경우 길이를 넣어줘서 사용한다.

stoi를 이용해 string을 int로 바꾸기

stoi를 이용하면 string을 int로 바꿀 수 있다. 인자로 int를 넣어준다.

queue sorting 하기

sort를 이용하면 deque, array 등을 정렬할 수 있다. 비교자를 사용하지 않을 경우 기본이 오름차순인 것을 기억하자! 내림차순으로 정렬할 경우 아래와 같은 함수를 세번째 인자로 넣어준다.

bool desc_comp(int a, int b) {
	return a > b;
}

정답 예시

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

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    deque<int> q;
    
    for(int i = 0; i < operations.size(); i++) {
        string target = operations[i];
        
        if(target[0] == 'I') {
            int value = stoi(target.substr(2));
            q.push_back(value);
            sort(q.begin(), q.end());
        } else {
            if(target[2] == '1') {
                if(q.size() != 0) {
                    q.pop_back();
                }
            } else {
                if(q.size() != 0) {
                    q.pop_front();
                }
            }
        }
    }
    
    if(q.size() == 0) {
        answer.push_back(0);
        answer.push_back(0);
        return answer;
    }
    
    answer.push_back(q.back());
    answer.push_back(q.front());
    
    return answer;
}
profile
구름위 개발자

0개의 댓글