priority_queue 우선순위 큐 활용

명예의 전당의 최하위 점수를 매일 기록해 반환하는 문제이다.

즉 k가 3이라고 한다면 탑3를 매일 선정하고 그 중 최하위 점수를 answer 리스트에 저장해 반환하면 되는 문제인데 예시 경우에는 올바르게 작동했지만, 여러 테스트 케이스를 채첨해봤을 때 오류가 발생했었다.

 

 

*초기 오답 코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for(int i = 0; i < score.size(); ++i)
    {
        // 현재 score가 명예의 전당에 들지 못 할 경우
        if(pq.size() > 0 && score[i] < pq.top())
        {
            // 현재 명예의 전당 최하위 점수 저장
            answer.push_back(pq.top());
            continue;
        }
        // pq의 사이즈가 k 이상
        if(pq.size() >= k)
        {
            pq.pop();
            pq.push(score[i]);
        }
        // pq의 사이즈가 k 미만
        else
        {
            pq.push(score[i]);
        }
        
        // 명예의 전당 최하위 점수 저장
        answer.push_back(pq.top());
    }
    
    return answer;
}

• 문제가 되었던 부분은 for문 안에 첫 번째 조건문 score[i] < pq.top()이었다.
• 간과하고 있던 부분은 명예의 전당의 크기는 k이고, 이 k의 크기를 초과하지 않을 때는 모든 값이 명예의 전당 list에 저장되어야 하는데, 현재 코드에선 만약 첫 번째로 명예의 전당에 10의 값이 들어오고 두 번째에 1의 값이 들어온다면 list에 값이 저장되지 않을 것이고 결과적으로 k의 값이 정확하게 카운팅 되지 않는 문제가 발생한다.

 

 

*수정된 코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for(int i = 0; i < score.size(); ++i)
    {
        // pq의 사이즈가 k 이상
        if(pq.size() >= k)
        {
            // 현재 score가 pq의 최소 값보다 클 때만 명예의 전당에 값 저장
            if(score[i] > pq.top())
            {
                pq.pop();
                pq.push(score[i]);    
            }
        }
        // pq의 사이즈가 k 미만
        else
        {
            pq.push(score[i]);
        }
        
        // 명예의 전당 최하위 점수 저장
        answer.push_back(pq.top());
    }
    
    return answer;
}

• 명예의 전당 list에 k만큼 값들이 차있을 때만 score[i] > pq.top()  점수가 명예의 전당에 있는 최소 점수보다 크면 값을 갱신하도록 수정하였다.
• 수정된 코드는 list의 사이즈가 k가 되기 전에는 값을 무조건 list에 저장하게 되고, k 이상이면 list의 최소 값보다 큰 값만 저장될 수 있음으로 문제에 맞게 해결되었다.

 

 

*multiset으로 문제 풀이

#include <string>
#include <vector>
#include <set>

using namespace std;

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    multiset<int> topList;
    
    for(int i = 0; i < score.size(); ++i)
    {
        // k를 초과하지 않을 때
        if(i < k)
        {
            topList.insert(score[i]);
        }
        // k를 초과할 때
        else 
        {
            // 현재 스코어가 topList의 최소 값보다 크다면
            if(score[i] > *topList.begin())
            {
                topList.erase(topList.begin());
                topList.insert(score[i]);
            }
        }
        
        //현재 topList의 최소 값을 answer에 저장
        answer.push_back(*topList.begin());
    }
    
    return answer;
}

• 다른 사람 문제 풀이를 보던 중 multiset으로 해결한 사람이 있어 참고해봤다.

 

그렇다면 priority_queue와 multiset 중에 어떤 컨테이너로 문제를 해결하는게 좋을까?

 

두 컨테이너 모두 삽입과 삭제 연산이 O(log n)으로 빠른 속도를 가지고 있다.

priority_queue는 내부 요소에 직접 접근하거나 특정 요소를 삭제하는 연산이 불가능하다.(우선 순위에 따른 삭제는 가능)

multiset은 반복자로 특정 값이 몇 번 저장되어있는지 확인 가능하고 특정 값을 삭제하거나 범위 삭제를 할 수 있다.

 

이 문제에서는 매일 "명예의 전당"의 최하위 점수만 발표하고, 새로운 점수를 추가하거나 교체하는 연산이 중심임으로 priority_queue가 더 적합해 보인다.

만약 특정 점수의 존재 여부를 확인하거나 특정 값을 삭제하는 등 추가적인 메서드 기능들이 필요하다고 한다면 multiset을 활용하는게 더 좋아보인다.

 

https://dong-grae.tistory.com/92

priority_queue