프로그래머스 문제 - 이중우선순위큐

프로그래머스 이중우선순위큐 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

1,000,000개 이하의 문자열 배열이 주어집니다.
연산을 위한 해석이 있습니다.

주어진 연산을 토대로 이중우선순위큐 배열을 완성시킨 후 최대값과 최소값을 출력해야 합니다.

문제 풀이

사실 우선순위 큐를 사용하면 짧고 쉽게 풀이가 가능한 문제입니다.
하지만 우선순위 큐를 따로 만들어보고 싶어 우선순위 큐를 만들어서 문제를 풀어보았습니다.

노드를 이용하여 만들것이기 때문에 구조체를 활용하여 노드를 만들어줍니다.

struct Node
{
    int value;
    Node* prev;
    Node* next;
};
    
public:
    Node* head;
    Node* tail;
    int size = 0;

값을 배열에 넣을 시 오름차순으로 넣기 위하여 노드의 값들을 비교하며 삽입해줍니다.

void enqueue(int num)
{
    //아무 값이 들어있지 않으면 첫 노드를 추가한다.
    if(head == nullptr)
    {
        Node* n = new Node();
        n->value = num;
        head = n;
        tail = n;
        head->prev = head;
        head->next = tail;
        tail->prev = head;
        tail->next = tail;
        size++;
    }
    else
    {
        Node* n = new Node();
        n->value = num;
        //값이 head보다 작거나 tail 보다 크면 바로 넣어줌
        if(n->value <= head->value)
        {
            head->prev = n;
            n->next = head;
            n->prev = n;
            head = n;
        }
        else if(n->value >= tail->value)
        {
            tail->next = n;
            n->prev = tail;
            n->next = n;
            tail = n;
        }
        else
        {
            Node* curNode = head;
            //오름차순으로 노드를 정렬하기 위하여 앞뒤 값을 비교하여 노드를 넣음
            while(curNode != nullptr)
            {
                if(curNode->value < num)
                {
                    if(curNode->next == tail)
                    {
                        curNode->next = n;
                        n->prev = curNode;
                        n->next = tail;
                        tail->prev = n;
                        break;
                    }
                    else
                    {
                        curNode = curNode->next;
                    }
                }
                else
                {
                    curNode->prev->next = n;
                    n->prev = curNode->prev;
                    curNode->prev = n;
                    n->next = curNode;
                    break;
                }
            }
        }
        size++;
    }
    cout << endl;
}

앞부분과 뒷부분의 값을 빼는 경우가 존재하기 때문에 head와 tail의 노드들을 제거하는 코드를 만들었습니다.
배열에 노드가 없다면 return을 해줍니다.

void dequeue(int num)
{
    if(size == 0)
    {
        return;
    }
    if(size == 1)
    {
        head = nullptr;
        tail = nullptr;
        size--;
        return;
    }
    if(num == 1)
    {
        tail = tail->prev;
        tail->next = tail;
    }
    else
    {
        head = head->next;
        head->prev = head;
    }
    size--;
}

전체 코드

이번 문제는 우선순위 큐를 사용하면 쉽게 풀 수 있지만 사용하지 않고 링크드리스트를 사용하여 우선순위 큐를 제작하였습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

class LinkedlistQueue
{
    struct Node
    {
        int value;
        Node* prev;
        Node* next;
    };
    
public:
    Node* head;
    Node* tail;
    int size = 0;
    
    void enqueue(int num)
    {
        //아무 값이 들어있지 않으면 첫 노드를 추가한다.
        if(head == nullptr)
        {
            Node* n = new Node();
            n->value = num;
            head = n;
            tail = n;
            head->prev = head;
            head->next = tail;
            tail->prev = head;
            tail->next = tail;
            size++;
        }
        else
        {
            Node* n = new Node();
            n->value = num;
            //값이 head보다 작거나 tail 보다 크면 바로 넣어줌
            if(n->value <= head->value)
            {
                head->prev = n;
                n->next = head;
                n->prev = n;
                head = n;
            }
            else if(n->value >= tail->value)
            {
                tail->next = n;
                n->prev = tail;
                n->next = n;
                tail = n;
            }
            else
            {
                Node* curNode = head;
                //오름차순으로 노드를 정렬하기 위하여 앞뒤 값을 비교하여 노드를 넣음
                while(curNode != nullptr)
                {
                    if(curNode->value < num)
                    {
                        if(curNode->next == tail)
                        {
                            curNode->next = n;
                            n->prev = curNode;
                            n->next = tail;
                            tail->prev = n;
                            break;
                        }
                        else
                        {
                            curNode = curNode->next;
                        }
                    }
                    else
                    {
                        curNode->prev->next = n;
                        n->prev = curNode->prev;
                        curNode->prev = n;
                        n->next = curNode;
                        break;
                    }
                }
            }
            size++;
        }
        cout << endl;
    }
    
    void dequeue(int num)
    {
        if(size == 0)
        {
            return;
        }
        if(size == 1)
        {
            head = nullptr;
            tail = nullptr;
            size--;
            return;
        }
        if(num == 1)
        {
            tail = tail->prev;
            tail->next = tail;
        }
        else
        {
            head = head->next;
            head->prev = head;
        }
        size--;
    }
};

vector<int> solution(vector<string> operations) {
    vector<int> answer;
    LinkedlistQueue* linkedQueue = new LinkedlistQueue();
    for(string str : operations)
    {
        if(str[0] == 'I')
        {
            str = str.substr(2, str.size()-2);
            int num = stoi(str);
            linkedQueue->enqueue(num);
        }
        else
        {
            str = str.substr(2, str.size()-2);
            int num = stoi(str);
            linkedQueue->dequeue(num);
        }
    }
    if(linkedQueue->head == nullptr)
    {
        answer.push_back(0);
        answer.push_back(0);
    }
    else
    {
        answer.push_back(linkedQueue->tail->value);
        answer.push_back(linkedQueue->head->value);
    }

    return answer;
}

출저

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