(C++) - 프로그래머스(고득점 kit - 스택/큐) : 주식가격 답

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

코딩테스트 연습 - 기능개발

stack을 이용한 문제였습니다.

풀이방법

 두 인덱스 사이의 차이는 초로 환산될 수 있습니다. 예를 들어 0번 인덱스의 price와 1번 인덱스의 price는 1초의 차이가 있습니다. 이를 이용해 stack에 price의 인덱스를 넣는 방식을 사용했습니다. 

 1. price[stack.top()] > price[i] 인동안 즉 가격이 떨어졌다면

 answer[stack.top()] = i - s.top()  //이는 가격이 떨어지지 않았던 시간을 대입해줍니다.

 

 2. 떨어진 구간의 시간들을 다 넣었으면 stack.empty()가 될 때까지 

 answer[stack.top()] = prices.size() - s.top() - 1 후

 stack.pop() 해줍니다.

Code

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> prices) {
    int pSize = prices.size();
    vector <int> answer(pSize);
    stack <int> s;
    for(int i = 0; i < pSize; i++){
        while(!s.empty() && prices[s.top()] > prices[i]){
            answer[s.top()] = i - s.top();
            s.pop();
        }
        s.push(i);
    }
    while(!s.empty()){
        answer[s.top()] = pSize - s.top() - 1;
        s.pop();
    }
    return answer;
}