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

0

프로그래머스

목록 보기
64/128
post-thumbnail

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

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;
}
profile
Be able to be vulnerable, in search of truth

0개의 댓글