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

 

프로그래머스

 

• 문제: 우선순위큐에 저장되어 있는 연산 명령어를 이용해 우선순위큐 데이터 추가 및 삭제
• 입력: 연산 명령어가 저장되어 있는 operations 배열
• 출력: [max, min]

 

풀이1️⃣ - 오답

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

using namespace std;

int cnt=0;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    priority_queue <int, vector<int>, less<int>> max_pq;
    priority_queue <int, vector<int>, greater<int>> min_pq;
    
    for (int i=0;i<operations.size();i++){
        if (operations[i][0] == 'I'){
            int num = stoi(operations[i].substr(2));
            max_pq.push(num);
            min_pq.push(num);
            cnt++;
            
        } else if (operations[i][0] == 'D'){
            if (cnt <= 0) break;
            
            if (operations[i][2] == '1'){ // 최댓값 삭제
                max_pq.pop(); 
                cnt--;
            } else if (operations[i][2] == '-'){ // 최솟값 삭제
                min_pq.pop();
                cnt--;
            }
        }
    }
    
    if  (cnt > 0){
        answer.push_back(max_pq.top());
        answer.push_back(min_pq.top());
    } else {
        answer.push_back(0);
        answer.push_back(0);
    }
    
    
    return answer;
}

 

• max_pq, min_pq의 priority_queue에 insert되는 원소 저장
• 최댓값 삭제는 max_pq.pop()
• 최솟값 삭제는 min_pq.pop()
• 남아 있어야 하는 원소의 개수를 cnt 변수에 저장
• cnt가 0이면 queue가 emtpy인 것으로 간주해 [0,0]을 저장하고, 0보다 크면 max_pq와 min_pq의 top에 있는 원소를 저장

이런 로직을 가지고 풀었더니...

테스크 케이스 3,4,5번만 통과하고 나머지는 실패라는 결과를 얻었다^!%

친구가 테스트 케이스 추가되고 원래 맞았던 코드가 틀렸다고 했는데 바로 이 상황이구나 싶었다 HAHA

 

이렇게 된 이상 multiset 자료구조를 사용할 수 밖에 없다!!

 

풀이2️⃣ 

#include <string>
#include <vector>
#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++){
        if(operations[i][0]=='I'){
            int num = stoi(operations[i].substr(2));
            ms.insert(num);
        } else if(!ms.empty()){
            if(operations[i][2]=='-'){ // 최솟값 삭제
                ms.erase(ms.begin());
            }
            else{ // 최댓값 삭제
                ms.erase(--ms.end());
            }
        }
    }
    if(ms.empty()){
        answer.push_back(0);
        answer.push_back(0);
    }
    else{
        answer.push_back(*(--ms.end()));
        answer.push_back(*ms.begin());
         }
    return answer;
}

 

multiset을 이용해 풀었더니...

정답!

 

multiset을 사용한 이유는 모든 원소에 접근 가능해 원하는 원소만 삭제할 수 있기 때문이다. 주의할 점은 원소를 알고 있으면 원소를 적어 삭제하거나 iterator를 사용해 삭제해야 한다는 점이다.

 

💡 이 문제의 핵심은
     1. multiset의 사용
     2. 문자열 파싱 시 char과 integer구분

이 두 가지를 들고 싶다. 왜냐하면 제가 이 두 가지 때문에 골치 아팠어요