[L3] 프로그래머스 이중우선순위큐 C++ 우선순위 큐, 해시맵

리뷰

프로그래머스

 

백준에 동일한 문제가 있다. min_heap과 max_heap을 각각 사용해 주고, 해시맵을 통해 해당 숫자가 존재하는지 여부를 체크하면 된다, 정수형 배열을 사용해도 될 것 같은데, 입력되는 수의 범위가 제한사항에 적혀있지 않아 해시맵을 사용하는 것이 안전해 보인다.

 

 

전역 변수

• dic : 현재 숫자가 존재하는지 여부를 체크할 해시맵, key는 숫자, value는 해당 숫자의 개수를 의미한다.

 

함수

없음

 

 

문제풀이

1. 최소값과 최대값을 우선순위로 저장할 우선순위큐 min_pq, max_pq를 초기화 해준다.
2. operations벡터를 참조하여 공백을 기준으로 op, val을 분리해 준다.
3. 정수형 변수 n을 문자열 val을 정수로 바꾸어 초기화 해준다.
4. op가 I일 경우 min_pq와 max_pq에 해당 숫자를 각각 넣어준 후 dic의 n을 1만큼 증가시켜준다.
5. op가 D일 경우 val이 1인지 -1인지를 비교해 주어야 한다, 1이면 max_pq에서, -1이면 min_pq에서 값을 제거해 준다.
6. 값을 제거할 때 만약 해당 pq들의 top이 dic에 존재하는지 체크를 해준다.
7. 만약 해당 값이 dic에 존재하지 않는 상태라면 pop을 해주고 다음 숫자를 확인해 준다.
8. 만약 dic에 존재하는 값이 나왔다면 dic에서 해당 숫자를 1만큼 감소시켜주고 pq에서는 pop처리를 해준다.
9. for문이 끝났다면 각 pq에 존재하는 dic에 없는 숫자들을 제거해 준다.
10. 만약 pq가 비었다면 answer에 0을 추가해 주고, 비지 않았다면 answer에 최대값, 최소값을 push해준다.
11. answer벡터를 리턴 해준다.

 

참고 사항

없음

 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;
unordered_map<int, int> dic;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    priority_queue<int, vector<int>, greater<int>> min_pq;
    priority_queue<int> max_pq;
    for(const string& s : operations) {
        stringstream ss(s);
        string op, val;
        getline(ss, op, ' ');
        getline(ss, val, ' ');
        
        int n = stoi(val);
        if (op == "I") {
            min_pq.push(n);
            max_pq.push(n);
            dic[n]++;
        } else {
            if (val == "1") {
                while (!max_pq.empty()) {
                    if (!dic[max_pq.top()]) {
                        max_pq.pop();
                        continue;
                    } else {
                        dic[max_pq.top()]--;
                        max_pq.pop();
                        break;
                    }
                }
            }
            else {
                while (!min_pq.empty()) {
                    if (!dic[min_pq.top()]) {
                        min_pq.pop();
                        continue;
                    } else {
                        dic[min_pq.top()]--;
                        min_pq.pop();
                        break;
                    }
                }
            }
        }
    }
    
    while (!max_pq.empty() && !dic[max_pq.top()]) max_pq.pop();
    while (!min_pq.empty() && !dic[min_pq.top()]) min_pq.pop();
    
    if (!max_pq.empty()) answer.push_back(max_pq.top());
    else answer.push_back(0);
    
    if (!min_pq.empty()) answer.push_back(min_pq.top());
    else answer.push_back(0);
    
    return answer;
}