[프로그래머스] [C++] 주식가격 (stack)

1. 문제

 

초단위로 기록된 주식 가격이 주어질때

 

가격이 떨어지지 않은 기간은 몇 초인지를 계산하여라

 

기록은 다음 기록이 있을시 1초가 지났다는걸 의미한다.

 

2. 스택 사용

모든 원소를 탐색하면서

 

스택에 넣는다

 

단, 스택에 넣기전에 top 보다 만약 해당 가격이 낮을 시 pop해주고

 

스택에 저장한 인덱스 벙보를 활용하여 몇초가 지났는지 파악한다.

 

이때 기록배열에 -1을 넣으면 자연스럽게 마지막 원소까지 해결된다.

(단 -1일때 len의 길이는 -1 해줘야한다. 임의로 들어간 원소이기 때문이다.)

 

 

3. 코드

이것은 처음 제출한 코드인데, 인덱스 0을 따로 스택에 먼저 넣지 않아도 잘작동한다.

즉, 필요없는 코드를 작성했다는 것 이다.

#include <string>
#include <vector>
#include <stack>
#include <utility>
 
using namespace std;
 
vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());
    stack<pair<int, int> > st;
    st.push(make_pair(prices[0], 0));
    prices.push_back(-1);
    
    for(int i = 1; i < prices.size(); i++)
    {
        while(!st.empty() && st.top().first > prices[i])
        {
            int index = st.top().second;
            int len = i - index; 
            st.pop();
            if(i == (prices.size() -1))
                len--;
            answer[index] = len;
        }
        st.push(make_pair(prices[i], i));
    }
    return answer;
}

Algorithm/StockPrice.cpp at master · Nor-s/Algorithm (github.com)

Nor-s/Algorithm

programmers.co.kr/learn/courses/30/lessons/42584

코딩테스트 연습 - 주식가격