Programmers - 이중우선순위큐

---

title: Programmers - 이중우선순위큐
date: 2022-07-28
tags:

• Algorithm

---

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

문제 요약

기존의 우선순위 큐와 다르게 가장 뒤에 있는 원소의 삭제까지 자유로운 새로운 자료구조를 만든다.
삽입, 최대값 삭제, 최소값 삭제의 연산만 있을 때, 최종적으로 최대값과 최소값을 return한다.

문제 풀이

문제에서 제시된 조건을 만족하는 자료구조처럼 동작하는 알고리즘을 만들면 된다.
처음에는 Priority queue를 이용하려고 하였으나, 후미 삭제에서 overhead가 크다는 것을 알았다.
vector를 이용하기에는 중간에 삽입할 때 overhead가 커질 것이며, 이로 인하여 LinkedList 방식인 List를 사용하였다.


처음부터 비교할 필요가 없다. 앞에서 n개를 삽입, 뒤에서 n개를 삭제하고 최종적으로 a개가 남아있다고 하자.
그러면 n개를 삭제한 시점까지는 볼 필요가 없다. 어차피 삽입을 하여도 전부 삭제할 것이다.
그러므로 우선 연산을 조회하며, List에 들어가는 원소의 개수가 0개가 되는 가장 늦은 시점을 확인한다.
그 시점 이후부터 연산을 진행하면 된다.
삽입의 경우, 앞에서부터 비교하여 삽입한다.
삭제의 경우, 선두 혹은 후미의 값을 삭제하는 것이다. List의 함수를 사용하여 삭제해준다.


좋은 성능을 보였으나, 실제로 이러한 자료구조를 만들어 사용한다면 고려할 것이 많다.
훨씬 많은 데이터가 삽입, 삭제가 반복될 것이며 미래의 데이터를 예측할 수 없다.
이러한 구조의 자료구조를 만든다면 삽입 과정에서 적절한 위치를 찾기 위해 순차 탐색을 진행한다.
포인터를 이용하여 Heap을 관리하는 것이 더욱 적절할 것이다.
탐색은 O(logn)의 시간 안에 찾을 수 있을 것이다. 삽입 후 정렬의 과정도 시간 복잡도가 그리 크지 않을 것이다.
각 노드의 용량이 크다면, 노드를 아무데나 할당한 후, 이 위치를 가리키는 포인터를 이용할 수도 있을 것이다.
Leaf 삭제는 바로 이루어지나, Root 삭제 후 정렬이 필요하다.
이 경우에도 동일하게 포인터를 이용하여 가리키는 위치만 바꾸면 정렬이 더욱 용이해질 것이다.

프로그램

#include <string>
#include <vector>
#include <algorithm>
#include <list>

using std :: vector ;
using std :: string ;
using std :: list ;

vector < int > solution ( vector < string > operations )
{
    vector < int > answer ( 2 , 0 ) ;
    int iStartIndex = -1 ;
    int iOperationSize = operations.size () ;
    int iTemp = 0 ;
    list < int > pqList ;



    for ( int i = 0 ; i < iOperationSize ; ++i )            // Find start index. At this order, queue is empty
    {
        if ( 'D' == operations [ i ] [ 0 ] )
            iTemp = std :: max ( 0 , iTemp - 1 ) ;
        else
            ++ iTemp ;

        if ( 0 == iTemp )
            iStartIndex = i ;
    }
    for ( int i = iStartIndex + 1 ; i < iOperationSize ; ++i )
    {
        int iValue = stoi ( operations [ i ].substr ( 2 , operations [ i ].size () - 2 ) ) ;
        bool bInsert = true ;

        if ( 'I' == operations [ i ] [ 0 ] )
        {
            for ( auto iter = pqList.begin () ; iter != pqList.end () ; ++ iter )
            {
                if ( iValue >= * iter )
                {
                    pqList.emplace ( iter , iValue ) ;
                    bInsert = false ;

                    break ;
                }                
            }

            if ( bInsert )                    // iValue is minimum value
            {
                pqList.emplace_back ( iValue ) ;
            }

            continue ;
        }

        if ( 1 == iValue )                    // Found iStartIndex, so pqList must not empty
            pqList.pop_front () ;
        else
            pqList.pop_back () ;
    }

    if ( ! pqList.empty () )
    {
        answer [ 0 ] = pqList.front () ;
        answer [ 1 ] = pqList.back () ;
    }


    return answer ;
}