프로그래머스_코딩테스트 연습_스택/큐_주식가격

문제 이름 : 주식 가격

문제 유형 : 스택(Stack)

작성 언어 : C++

 

• 주식가격

문제 설명

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

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

prices                                                                        return

[1, 2, 3, 2, 3]

[4, 3, 1, 1, 0]

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

 

 

풀이 : 정확성과 효율성 둘 다 체크하는문제

시간에 따른 주식가격 전부가 입력배열로 주어지므로

현재의 주식가격과 이전의 주식가격을 비교해나가야한다.

주식의 가격이 오르고있다면 스택에넣어주고

주식의 가격이 내려가고있다면 스택에 넣어두었던 직전가격과 비교하여 얼마동안 가격이 떨어지지않았는지를 answer 에 저장하여 출력한다.

 

#include <string>
#include <vector>
#include <stack>
#include <iostream>

using namespace std;

vector<int> solution(vector<int> prices){
    int size = prices.size();
    
    vector<int> answer(size);
    stack<int> st;
    
    for (int i=0; i<size; i++)
    {
        while (!st.empty() && prices[st.top()] > prices[i]) //스택에 저장된 마지막주식가격보다 현재가격이 작으면
        {                                                   //(가격이 점점 떨어질때)
            auto top = st.top();    //마지막 주식가격 시각을 저장
            st.pop();               //가격이떨어졌기때문에 
            answer[top] = i - top;  //얼마동안 떨어지지않았는지 answer에 써준다.
        }
        st.push(i); //가격이 오르고있을때는 스택에저장
    }
    
    while (!st.empty()) //스택이 남아있는경우 (끝까지 가격이 떨어지지않음)
    {                   //스택에 남아있었던 전체기간 answer에 써주기
        auto top = st.top();
        st.pop();
        answer[top] = size - 1 - top;
    }
    
    return answer;
}

 

 

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

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