[프로그래머스] 주식가격⭐

[프로그래머스] 주식가격

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

• 스택 사용 풀이

input: 1, 2, 3, 2, 3
output: 4, 3, 1, 1, 0

• answer -1로 초기화
  answer = {-1, -1, -1, -1, -1}

• 스택 원소 <가격, 가격 배열 내 인덱스>

• 스택 내 원소 오름차순 유지 하도록 push
  pop할 때 떨어지지 않은 시간(answer)계산 = 현재 인덱스(i) - 가격 배열 내 인덱스

  • i = 0, st: (1,0)
  • i = 1, st: (1,0) (2,1)
  • i = 2, st: (1,0) (2,1) (3,2)
  • i = 3, st: (1,0) (2,1) -> (3,2) pop, answer[2] = 3-2 = 1
    st: (1,0) (2,1) (2, 3)
  • i = 4, st: (1,0) (2,1) (2,3) (3,4)
  • answer = {-1, -1, 1, -1, -1}

• 스택에 남은 모든 원소 하나씩 pop하기
  pop할 때 떨어지지 않은 시간(answer)계산 = 마지막 인덱스(4) - 가격 배열 내 인덱스

  • st: (1,0) (2,1) (2,3) -> (3,4) pop, answer[4] = 4-4 = 0
  • st: (1,0) (2,1) -> (2,3) pop, answer[3] = 4-3 = 1
  • st: (1,0) -> (2,1) pop, answer[1] = 4-1 = 3
  • st: -> (1,0) pop, answer[0] = 4-0 = 4
  • answer = {4, 3, 1, 1, 0}

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

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