[Algorithm] Programmers :: 이중우선순위큐

https://programmers.co.kr/learn/courses/30/lessons/42628?language=cpp 

코딩테스트 연습 - 이중우선순위큐

vector<string> split(string str, char Delimiter) {
    istringstream iss(str);             // istringstream에 str을 담는다.
    string buffer;                      // 구분자를 기준으로 절삭된 문자열이 담겨지는 버퍼
 
    vector<string> result;
 
    // istringstream은 istream을 상속받으므로 getline을 사용할 수 있다.
    while (getline(iss, buffer, Delimiter)) {
        result.push_back(buffer);               // 절삭된 문자열을 vector에 저장
    }
 
    return result;
}
 
vector<int> solution(vector<string> operations) {
    // I 숫자 : 주어진 숫자를 삽입
    // D 1 : 큐에서 최댓값 삭제
    // D -1 : 큐에서 최솟값을 삭제
    
    vector<int> answer;
    vector<string> temp;
    int count = 0;
 
    priority_queue<int, vector<int>, greater<int> > minPQ; 
    priority_queue<int, vector<int>, less<int> > maxPQ; 
    
    for (int i = 0; i < operations.size(); i++)
    {
        temp = split(operations[i], ' ');
        string operation = temp[0];
        int num = stoi(temp[1]);
 
        if (operation == "I")
        {
            minPQ.push(num);
            maxPQ.push(num);
            count++;
        }
 
        if (operation == "D")
        {
            if (num == 1 && count > 0) // 최댓값 삭제
            {
                maxPQ.pop();
                count--;
            }
 
            if (num == -1 && count > 0) // 최소값 삭제
            {
                minPQ.pop();
                count--;
            }
        }
 
        if (count == 0) // count가 0이면, 두 큐에는 원소가 한개도 없어야한다. 그러므로 다 비워준다.
        {
            while (!maxPQ.empty())
            {
                maxPQ.pop();
            }
            while (!minPQ.empty())
            {
                minPQ.pop();
            }
        }
    }
 
    if (count == 0)
    {
        answer.push_back(0);
        answer.push_back(0);
    }
    else
    {
        answer.push_back(maxPQ.top());
        answer.push_back(minPQ.top());
    }
    
    return answer;
}

 

이중우선순위큐라는 새로운 유형의 문제다. string으로 주어지는 명령어를 토대로 작업을 수행하다가 최종적으로 남은 큐의 최대값,최소값을 리턴하면 된다. 한개만 남았으면 그 한개가 최대값이자 최소값이고 아예 큐가 비어있다면 0,0을 리턴하면 된다. 공백기준 문자열 나누기는 많은 예제가 있으니 알아서 나누면 된다. 

위 코드에서는 istringstream을 사용해서 나눴지만, 이 문제같은 경우 공백이 무조건 1번째 인덱스에 있기 때문에 substr을 이용해서 0번째를 바로 명령어로 추출하고 1번째 이후부터 string의 size()-1까지를 숫자로 추출하면 된다.

 

이 문제는 기준이되는 우선순위큐 한개(이하 standPQ)를 서로 반대쪽 우선순위큐(최대값,최소값) 두개로 표현해서 해결한다.  즉, maxPQ.top()과 minPQ.top() 은 standPQ의 서로 양쪽 끝이다.(PQ는 priority queue이다.)

위 코드에서 count는 standPQ의 실제 원소개수라고 생각하면 된다. 그렇기때문에 I명령의 작업을 수행할 때(아마 Input의 약자이지 않을까 싶다) maxPQ와 minPQ에 각각 숫자를 넣더라도 count는 1만 증가다.

실제로 standPQ에는 한개만 들어가는 형식이기 때문이다.

 

D 1과 D -1은 각각 최대값,최소값 삭제이기 때문에 해당사항에 맞는 큐에서 pop을 한다. 당연히 내용물이 있어야 pop을 하기 때문에 count값이 0 초과일때 해당 작업을 수행한다. 일련의 명령을 수행했는데 count == 0이라면 standPQ에는 원소가 한개도 없다는 뜻이다. 그러면 maxPQ와 minPQ에도 원소가 있어서는 안된다. 두 큐는 standPQ를 서로 반대쪽으로 표현한 PQ이기 때문이다. 그렇기 때문에 count == 0이라면 두 큐를 깔끔하게 비워주자.

 

위의 로직으로 모든 명령을 수행하면 standPQ에 원소가 없던가, 1개이상이 있던가 할 것이다.

원소가 없다면 그냥 0,0을 넣어 리턴시키면 되고 1개이상이라면 각 큐의 top을 넣어 리턴시키면 된다.

standPQ에 원소가 1개라면, 각 큐에는 그 원소가 무조건 들어있다. 그래서 그대로 top을 넣어 리턴시키면 동일한 값을 리턴하기 때문에 문제가 생기지 않는다.

 

코드가 잘 이해가 안된다면, 이미 언급했다시피 maxPQ,minPQ는 그저 standPQ 한개를 각 반대쪽에서 표현한 두개의 큐일 뿐이고, count는 standPQ의 원소개수라는것만 인지하고 코드를 보면 이해가 된다. 사실 코드는 아주 단순하니까..