[프로그래머스]힙(Heap) : 이중우선순위큐 (level 3) (c++)

https://programmers.co.kr/learn/courses/30/lessons/42628

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

 

방법 1: int배열 사용

#include <string>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;

int datas[1000000];
 
vector<int> solution(vector<string> operations) {

    int start = 0, end = 0;
    for (string line : operations)
    {
        // 명령어, 숫자 받아오기
        stringstream ss(line);
        char op;
        int num;
        ss >> op >> num;

        // 명령어 I : 끝 인덱스 자리에 숫자 삽입, 끝 인덱스 증가
        if (op == 'I')
        {
            datas[end] = num;
            ++end;
        }
        // 명령어 D 이고 데이터가 남아있다면
        else if(end - start > 0)
        {
            // 최대값 삭제 : 시작 인덱스 증가
            if (num > 0)
            {
                ++start;
            }
            // 최소값 삭제 : 끝 인덱스 감소
            else
            {
                --end;
            }
        }

        // 내림차순 정렬
        sort(datas + start, datas + end, [](int a, int b) {
            return a > b;
            });
    }
    
    // 시작인덱스 == 끝 인덱스 : 남은 데이터가 없다
    if (end - start == 0)
    {
        return { 0, 0 };
    }

    // 최대값, 최소값 반환
    return {datas[start], datas[end - 1]};
}

 

방법 2: int벡터 사용

#include <string>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;

vector<int> solution(vector<string> operations) {

    vector<int> datas;

    for (string line : operations)
    {
        // 명령어, 숫자 받아오기
        stringstream ss(line);
        char op;
        int num;
        ss >> op >> num;

        // 삽입 명령어
        if (op == 'I')
        {
            datas.push_back(num);
        }
        // 삭제 명령어이고 데이터가 남아있다면
        else if(datas.size() > 0)
        {
            // 최대값 삭제 : 가장 앞에 있는 값 삭제
            if (num > 0)
            {
                datas.erase(datas.begin());
            }
            // 최소값 삭제 : 가장 뒤에 있는 값 삭제
            else
            {
                datas.pop_back();
            }
        }

        // 내림차순 정렬
        sort(datas.begin(), datas.end(), [](int a, int b) {
            return a > b;
            });
    }
    
    // 시작인덱스 == 끝 인덱스 : 남은 데이터가 없다
    if (datas.size() == 0)
    {
        return { 0, 0 };
    }

    // 최대값, 최소값 반환
    return { *datas.begin(), *(datas.end() - 1) };
}

 

 

벡터를 사용한다면 공간 절약이 될 것이다.

명령어를 사용할 때마다 정렬을 하는 것이 포인트인 문제였다.