🖊️ 문제

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

🖊️ 풀이

일단 나는.. 문제 보자마자 n개 정렬된 상태로 유지하며 넣었다 뺐다 해야해서
무조건 우선순위 큐부터 생각했다
그래서
우선순위큐에 오름차순으로 넣어주고, 원소 개수 (k개)가 넘으면 pop()해주면
쉽게 관리될거라고 생각했당.

벡터에 냅-다 때려넣고 정렬해버리면 시간복잡도 어떻게 나올까 궁금했다

🖊️ 코드

우선순위 큐

#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>> temp;
    
    for (int i = 0 ; i < score.size() ; i++) {
        temp.push(score[i]);
        if (temp.size() > k) {
            temp.pop();
        }
        answer.emplace_back(temp.top());
    }
    
    return answer;
}

결과

벡터

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

using namespace std;

vector<int> solution(int k, vector<int> score) {
    vector<int> answer;
    vector<int> temp;
    
    for (int i = 0 ; i < score.size() ; i++) {
        temp.emplace_back(score[i]);
        sort(temp.begin(), temp.end());
        if (temp.size() > k) {
            temp.erase(temp.begin(), temp.begin() + (temp.size() - k));
        }
        answer.emplace_back(temp[0]);
    }
    
    return answer;
}

결과

흠..
우선순위 큐가 훨씬 좋군!!

우선순위큐는 삽입, 삭제 O(logN) 인데
stl의 sort함수는 O(n * logN)이니까
호호호