[L2] 프로그래머스 주식가격 C++ 우선순위 큐

리뷰

프로그래머스

 

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하는 문제

 

 

전역 변수

• v : 각 주식의 떨어지지 않은 기간을 저장하기 위한 정수형 배열

 

함수

없음

 

 

문제풀이

1. 정수  n을 prices벡터의 길이로 초기화 해준다.
2. pair<int, int>타입의 우선순위 큐 pq를 초기화 해준다, 해당 pq는 주식 가격 기준 내림차순이다.
3. n번의 for문을 개행해 준다.
4. pq가 비지 않았고, pq의 top이 prices의 i번째 인덱스 값보다 클 경우 pq에서 꺼내준다.
5. v배열의 해당 주식의 인덱스값을 현재 주식의 인덱스 - 해당 주식의 인덱스로 저장해 준다.
6. 현재 주식 가격 정보와 인덱스를 pq에 삽입해 준다.
7. 모든 반복문이 종료된 후에는 pq에 남아있는 주식 정보들을 v배열에 최신화 해주어야 한다.
8. 주식 정보를 하나씩 꺼내주고, v배열의 해당 주식 인덱스를 n - 1 - 주식의 인덱스로 최신화 해준다.
9. v배열에 담긴 n개의 주식 정보를 앞에서부터 순차적으로 answer벡터에 추가해 준다.
10. answer벡터를 리턴해 준다.

 

참고 사항

주식 정보를 한번에 다 받아오지 않고, i번째 주식 정보가 입력되었을때 실시간으로 처리해 주어야 한다.

 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;
int v[100000];

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    int n = prices.size();
    
    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < n; i++) {
        while (!pq.empty() && pq.top().first > prices[i]) {
            pair<int, int> cur = pq.top(); pq.pop();
            v[cur.second] = i - cur.second;
        }
        pq.push({prices[i], i});
    }
    
    while (!pq.empty()) {
            pair<int, int> cur = pq.top(); pq.pop();
            v[cur.second] = n - 1 - cur.second;
        }
    
    for (int i = 0; i < n; i++) answer.push_back(v[i]);
    
    return answer;
}