[프로그래머스/C++] 이중우선순위큐

 

 

문제

문제 설명

 

풀이

 

테스트 케이스의 예시가 적어서 그런지 vector에 숫자를 삽입 할 때, 이분 탐색으로 들어갈 위치만 잘 정해주니 쉽게 풀리는 문제였다.

​

[아이디어 정리]

1. vector 에 숫자를 삽입 할 때, 이분 탐색으로 삽입 될 위치를 계산한다.

​

2. 삭제 명령이 뜰 경우 최대 최소에 따라 vector의 맨 앞 숫자를 삭제하거나 맨 뒤의 숫자를 삭제한다.

 

 

Code

 

 

#include <string>
#include <vector>
using namespace std;

vector<int> answer;
void InsertNum(string num)
{
    int st, ed,mid;
    int reNum=stoi(num);
    st = 0;
    ed = answer.size()-1;
    while (st<=ed)
    {
        mid = (st+ed)/2;
        if (reNum>answer[mid])
        {
            st=mid+1;
        }
        else if(reNum<answer[mid])
        {
            ed=mid-1;
        }
        else
        {
            st=mid+1;
            break;
        }
    }
    answer.insert(answer.begin()+st,reNum);    
}
vector<int> solution(vector<string> operations) {
    string code, strNum;
    for (int i=0; i<operations.size(); i++)
    {
        code = operations[i].substr(0,1);
        strNum=operations[i].substr(2,operations[i].length());
        if (code=="I")
        {
            InsertNum(strNum);
        }
        if (code=="D")
        {
            if (answer.size()>0)
            {
                if (strNum=="1")
                {
                    answer.pop_back();
                }
                else
                {
                    answer.erase(answer.begin());
                }
            }
        }
    }
    vector<int> reAns(2,0);
    if (answer.size()>0)
    {
        reAns[0]=answer[answer.size()-1];
        reAns[1]=answer[0];
        return reAns;
    }
    return reAns;
}

 

---

 

테스트 케이스가 적어서 엄청 쉽게 풀린 문제였다.

 

프로그래머스