Programmers / 주식가격 / C++

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 주식가격 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

 

문제 설명

 

---

 

나의 풀이

 

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

vector<int> solution(vector<int> prices) {
    vector<int> answer;

    int idx = 0;

    for (int i = 0; i < prices.size(); i++) {
        queue<int> q;
        
        int cnt = 0;
        int x = prices[idx];

        for (int j = idx + 1; j < prices.size(); j++) {
            q.push(prices[j]);
        }
        
        while(!q.empty()) {
            if (x <= q.front()) {
                cnt++;
                q.pop();
            }
            else {
                cnt++;
                break;
            }
        }
        if (cnt > 0) answer.push_back(cnt);
        idx++;
    }
    
    answer.push_back(0);
    
    return answer;
}

 

처음에는 q에 원소를 넣고 하나씩 빼면서 가격이 떨어지면 그 시간을 넣는 방식으로 진행했다.

이 풀이는 queue가 의미가 없고 for 중첩이 되는 풀이라서 효율성에서 틀렸다.

 

#include <string>
#include <vector>
#include <deque>
using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size(), 0);
    deque<int> q;
    int size = prices.size(); 

    for (int i = 0; i < size; i++) {
        while (q.empty() != 1 && prices[q.front()] > prices[i]) {
            answer[q.front()] = i - q.front();
            q.pop_front();
        }
        q.push_front(i);
    }
    while (q.empty() != 1) {
        answer[q.front()] = size - 1 - q.front();
        q.pop_front();
    }

    return answer;
}

 

중첩을 하나 빼고 가격이 떨어질때 그 시간을 넣는 방식으로 풀었다.

---

※ 알아야 할 것

 

queue는 선입선출의 방식을 지원하고 stack은 후입선출의 방식을 지원한다. deque는 선입선출도 가능하고 후입선출도 가능하고 위 코드를 스택으로 바꿔도 풀린다. 하지만 필자는 queue랑 deque 메소드가 비슷해서 deque로 바꿔서 풀었다.