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

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

프로그래머스

 

 

stringstream을 통해 데이터 추출 후, deque를 이용해서 조건에 맞는 제일 큰 값, 제일 작은 값 pop 하여 진행했다. 흠... 통과되긴 했지만, 데이터 넣을 때마다 sort 하는 건 마음에 들지 않는다.

 

#include <string>
#include <vector>
#include <queue>
#include <sstream>
#include <algorithm>
using namespace std;

vector<int> solution(vector<string> operations) {

    deque<int> dq;
    char c;
    int n;
    for (int i = 0; i < operations.size(); i++)
    {
        stringstream ss(operations[i]);
        ss >> c;
        ss >> n;    

        if (c == 'D') 
        {
            if (!dq.empty()) 
            {
                if (n == 1) 
                {
                    dq.pop_front(); // 최댓값 삭제
                } else if (n == -1)
                {                    
                    dq.pop_back(); // 최솟값 삭제
                }
            }
        } else if (c == 'I')
        {
            dq.push_back(n); // 삽입
            sort(dq.begin(), dq.end(),greater<int>()); // 정렬

        }
    }
    
    vector<int> answer(2, 0);
    if (!dq.empty()) {
        answer[0] = dq.front(); // 최솟값
        answer[1] = dq.back(); // 최댓값        
    }
    
    return answer;
}

 

 

효율검사는 하지 않지만, std::lower_bound 함수를 이용해서 sort 대신 대체 해보았다.

 

결과적으로 봤을때 std::sort 함수는 퀵정렬을 기반으로 해서 평균 O(nlogn)의 탐색시간을 갖고, std::lower_bound는 이진탐색을 이용하고 있어서 평균 O(logn)을 갖는다고 한다. 결과적으로 조금 나아졌다.

 

 

#include <string>
#include <vector>
#include <queue>
#include <sstream>
#include <algorithm>
#include <iostream>
using namespace std;

vector<int> solution(vector<string> operations) {
    deque<int> dq;
    char c;
    int n;    
    
    for (int i = 0; i < operations.size(); i++)
    {
        stringstream ss(operations[i]);
        ss >> c;
        ss >> n;    

        if (c == 'D') 
        {
            if (!dq.empty()) 
            {
                if (n == 1) 
                {
                    dq.pop_back(); // 최댓값 삭제
                } else if (n == -1)
                {                    
                    dq.pop_front(); // 최소값 삭제
                }
            }
        } else if (c == 'I')
        {
            auto it = lower_bound(dq.begin(), dq.end(), n); // 삽입 위치를 찾음
            dq.insert(it, n); // 삽입
        }
    }
    
    vector<int> answer(2, 0);
    if (!dq.empty()) {
        answer[1] = dq.front(); // 최솟값
        answer[0] = dq.back(); // 최댓값        
    }
    
    return answer;
}