알고리즘(C++) / 프로그래머스 level 3 : 이중우선순위큐

level 3 : 이중우선순위큐

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

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

 

코드

//프로그래머스 이중우선순위큐
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    vector <int> v;

    for (int i = 0; i < operations.size(); i++) {
        stringstream ss(operations[i]);
        int num;
        string s;
        ss >> s >> num;

        if (s == "I") {
            v.push_back(num);
            sort(v.begin(), v.end()); //정렬
        }
        else{
            if (v.empty())
                continue;
            //최댓값 삭제
            if (num == 1) {
                v.pop_back();
            }
            //최솟값 삭제
            else if (num == -1) {
                v.erase(v.begin());
            }
        }
    }

    if (v.empty()) {
        answer.push_back(0);
        answer.push_back(0);
    }
    else {
        answer.push_back(v[v.size() - 1]); //최댓값
        answer.push_back(v[0]); //최솟값
    }

    return answer;
}

int main() {
    vector <string> operations = { "I 7","I 5","I -5","D -1" };
    solution(operations);
    return 0;
}

 

설명

• stringstream으로 string을 s와 num으로 나눈다.
• s가 I라면  벡터에 숫자를 삽입한 후 오름차순으로 정렬한다.
• s가 D이고 num이 1이라면 가장 큰 수를 삭제한다. num이 -1이라면 가장 작은 수를 삭제한다. 이때 벡터에 아무것도 존재하지 않는다면 아무것도 삭제하지 않는다.
• operations의 크기만큼 반복한다. 
• 벡터에서 최댓값과 최솟값을 구하여 answer벡터에 push 한다. 

 

고찰

걸린 시간 : 30분

힙(Heap) 문제여서 우선순위 큐를 사용하여 문제를 풀었었지만 효율성 테스트 없었기 때문에 굳이 우선순위 큐를 사용하여 문제를 풀지 않았어도 된다. 그래서 벡터를 사용하여 쉽게 삭제하고 정렬하여 문제를 풀 수 있었다.

다른 사람의 풀이를 보니 multiset이라는 stl을 사용하였다. 중복된 key 값이 저장되고 자동으로 정렬되고 접근이 쉽다. 따라서 multiset으로 문제를 풀 수 도 있다. 

 

multiset 풀이 코드

#include <set>

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    multiset<int> ms;
    for (int i = 0; i < operations.size(); i++) {
        stringstream ss(operations[i]);
        int num;
        string s;
        ss >> s >> num;
        if (s == "I") {
            ms.insert(num);
        }
        else {
            if (ms.empty())
                continue;
            if (num == 1) {
                ms.erase(--ms.end());
            }
            else if (num == -1) {
                ms.erase(ms.begin());
            }
        }
    }

    if (ms.empty()) {
        answer.push_back(0);
        answer.push_back(0);
    }
    else {
        answer.push_back(*(--ms.end())); //최댓값
        answer.push_back(*(ms.begin())); //최솟값
    }

    return answer;
}

2021.09.06 - [알고리즘] - 알고리즘(C++) / STL : set, multiset

multiset과 set의 설명은 여기서 자세히 설명한다.