[프로그래머스] 이중 우선 순위 큐 / C++ 풀이 / 자료구조

풀이 전략

priority_queue 두 개를 활용해서 풀 수도 있을 것 같지만  포인터  복습할 겸 그냥 전부 구현했다. 

 

C++ 코드

#include <string>
#include <vector>

using namespace std;

typedef struct node node_t;
struct node {
    int val;
    node_t* lChild;
    node_t* rChild;
};

vector<int> vals;
void insert(node_t** p, int n);
void midfixInsertVal(node_t* p);
void removeMax(node_t** pp);
void removeMin(node_t** pp);

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    vals.clear();
    node_t* p = NULL;
    for (const auto& op : operations) {
        if (op[0] == 'I') {
            int num = stoi(op.substr(2));
            insert(&p, num);
            continue;
        }

        if (p == NULL) { //빈 큐에 데이터를 삭제하는 연산은 무시한다.
            continue;
        }

        if (op == "D 1") {
            removeMax(&p);
        }
        else {
            removeMin(&p);
        }
    }

    midfixInsertVal(p);

    if (vals.size() == 0) {
        return { 0,0 };
    }

    return { vals.back(), vals.front() };
}

void insert(node_t** p, int n) {
    if (*p != NULL) {
        if ((*p)->val > n) {
            insert(&(*p)->lChild, n);

        }
        else {
            insert(&(*p)->rChild, n);
        }

        return;
    }

    *p = new node_t{ n, NULL, NULL };
}

void removeMax(node_t** pp) {
    if ((*pp)->rChild == NULL) {
        node_t* del = *pp;
        *pp = (*pp)->lChild;
        free(del);
        return;
    }

    while ((*pp)->rChild->rChild != NULL) {
        pp = &((*pp)->rChild);
    }

    node_t* del = (*pp)->rChild;
    (*pp)->rChild = ((*pp)->rChild->lChild);
    free(del);
}

void removeMin(node_t** pp) {
    if ((*pp)->lChild == NULL) {
        node_t* del = *pp;
        *pp = (*pp)->rChild;
        free(del);
        return;
    }

    while ((*pp)->lChild->lChild != NULL) {
        pp = &((*pp)->lChild);
    }

    node_t* del = (*pp)->lChild;
    (*pp)->lChild = ((*pp)->lChild->rChild);
    free(del);
}

void midfixInsertVal(node_t* p) {
    if (p != NULL) {
        midfixInsertVal(p->lChild);
        vals.push_back(p->val);
        midfixInsertVal(p->rChild);
    }
}

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

프로그래머스

 

느낀 점

트리 자료구조 구현 복습할 필요가 있다. 그리고 구현에 시간이 좀 걸렸는데 이 정도는 가볍게 구현해야 어디 가서 포인터 안다고 말을 할 수 있을듯...더 연습하자..^^;