99클럽 코테 스터디 3일차 TIL : 이중우선순위큐 (챌린저)

이중 우선순위큐를 구현하는 문제였다

-> max, min 두개에 접근 가능한 자료구조

 

그냥 간단하게 heap을 두개 만들어서 구현했다.

(max heap, min heap)

 

뭔가 더 간단하고 메모리효율이 좋은 방법이 있을것같긴한데,,, 일단 통과했으니까 됐다

---

1. 문자열 split -> sstream 이용해서 operation, operand 두개로 구분했다.

2. operation기준으로 switch문 사용

3. case I : min heap, max heap 각각에 operand를 push한다.

4. case D

    a. operand 가 양수일때 : max heap에서 pop, pop한 값을 min heap에서 찾아서 삭제 (vector이므로 removw, erase 이용)

    b. operand 가 음수일때: min heap에서 pop, pop한 값을 max heap에서 찾아서 삭제

 

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

using namespace std;

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    
    vector<int> minheap;
    vector<int> maxheap;
    for(int i = 0; i<operations.size(); i++){
        string instruction = operations[i];
        istringstream ss(instruction);
        string operation;
        string operand;
        ss >> operation >> operand;
        
        int num = stoi(operand);
        switch (operation[0]){
            case 'I':{
                minheap.push_back(num);
                push_heap(minheap.begin(), minheap.end(), greater<>{});
                maxheap.push_back(num);
                push_heap(maxheap.begin(), maxheap.end());
                break;
        }
            case 'D':{
                if(num > 0){
                    // delete maxheap
                    if(maxheap.size() < 1){
                        // empty heap
                        // nothing
                        break;
                    }else{
                        int max = maxheap[0];
                        pop_heap(maxheap.begin(), maxheap.end());
                        maxheap.pop_back();
                        minheap.erase(remove(minheap.begin(), minheap.end(), max),minheap.end());
                        make_heap(minheap.begin(), minheap.end(), greater<>{});
                    }
                }else{
                    //delte minheap
                    if(minheap.size() < 1){
                        // empty heap
                        // nothing
                        break;
                    }else{
                        
                        int min = minheap[0];
                        pop_heap(minheap.begin(), minheap.end(), greater<>{});
                        minheap.pop_back();
                        maxheap.erase(remove(maxheap.begin(), maxheap.end(), min),maxheap.end());
                        make_heap(maxheap.begin(), maxheap.end());
                    }
                }
                break;
            }
                
            
        }
        cout << endl;
        
    }
    
    
    if(minheap.size() < 1){
        // empty heap
        answer = {0, 0};
    }else{
        answer = {maxheap[0], minheap[0]};
    }
    
    
    
    return answer;
}

---

split방법을 몰라서 찾아봤다.. 이런점에서는 파이썬이 역시 편한것같다.

 

pop_heap할 때, compare를 따로 지정해줘야 하는 경우(여기서는 min heap) 꼭 같이 적어줘야한다!

이걸까먹어서 중간에 테스트케이스 안넘어가는거에 시간을 많이 사용했다.

 

remove와 erase에 대해 아직 잘 모르겠다..

일단 구글링에서 찾은 방법대로 해서 해결하긴 했는데... 왜 저렇게 나눠놨는지도 모르겠구,,,,,

애초에 vector라는거에 익숙해지질 않는다. 그냥 배열쓰면 안돼?? 대충 배열이랑 비슷한 느낌인것같긴한데,...