[프로그래머스 이중우선순위큐] c++ (풀이, 코드)

문제 링크

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

 

문제

 

풀이, 코드

처음에는 풀이를 하였을때 테스트 1에서 계속 틀리는 현상이 발견했다.. 이게 왜 틀린것인가..? 하는 의문이 들었다.

 

우리가 카운트를 할때 저는 따로 pqsize를 진행하여 delete가 되었을때 (최소든 최대든) 일단 전체의 크기에서 지워지는 것이니 -1을 하는것은 당연한 사실이다. 또한 insert를 할때도 +1을 하는 것은 사실

 

하지만 초기 틀렸던 이유는 

내림차순 PQ	오름차순 PQ
3	1
2	2
1	3

 

이러한 상태에서 내림차순 3,2,1이 지워졌다고 가정할때 "D 1","D 1","D 1"을 하게 되면 오름차순의 PQ는 그대로 남아있게 된다.

 

이것에 대해서 주의사항으로 만약에 pqsize가 0이 되었을때는 항상 두개의 priority queue를 비워주는 것을 진행해줘야 이 문제에 대해서 해결이 가능합니다.

 

아래는 풀이 코드 입니다.

 

#include <string>

#include <vector>

#include <queue>

using namespace std;

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

    vector<int> answer;

   

    priority_queue<int> down_pq; //내림차순 pq

    priority_queue<int,vector<int>, greater<int>> up_pq; //오름차순 pq

    int pqsize = 0;

   

    for(int i = 0; i < operations.size();i++){

        if(pqsize == 0){

            while(!up_pq.empty())

                up_pq.pop();

            while(!down_pq.empty())

                down_pq.pop();

        }

        if(operations[i][0] == 'I'){

            down_pq.push(stoi(operations[i].substr(2)));

            up_pq.push(stoi(operations[i].substr(2)));

            pqsize++;

        }else if (operations[i][0] == 'D' && pqsize > 0){ //삭제할때 들어온것에 대해서 처리해야함

            if(operations[i][2] == '-'){ //최솟값 삭제

                up_pq.pop();

            }else{ //최댓값삭제

                down_pq.pop();

            }

            pqsize--;

        }

    }

   

    //pqsize가 0보다 크다는 것은 존재하는것임

    if(pqsize > 0){

        answer.push_back(down_pq.top());

        answer.push_back(up_pq.top());

    }else{

        answer.push_back(0);

        answer.push_back(0);

    }

   

    return answer;

}

 

감사합니다.

 

 

 

 

개인적인 정리

1. stoi를 써라 왜 맨날 하나씩 함수를 만들고 있니..

int makeNumber(string s){

    int isMinus = 1;

    int num = 0;

    for(int i = 2;i < s.size();i++){

        if(s[i] == '-'){

            isMinus = -1;

        }else if('0' <= s[i] && s[i] <= '9'){

            num *= 10;

            num += s[i] - '0';

        }

    }

    return num * isMinus;

}

이러고 있는 나의 모습이 답답하다ㅋㅋㅋㅋㅋ

 

2. substr 사용 습관화 하기.