[프로그래머스] Level2 : 주식가격 - C++

문제

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

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

---

코드설명

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

 

for문은 prices.size()번 돌아간다. 매번 answer에 0을 push해준다.(index로 접근하기 위해서 미리 벡터를 0으로 초기화)

 

스택 s에는 prices[i](가격)과 인덱스(i)를 모두 넣어준다. 스택의 top의 가격이 현재 비교하는 prices[i]보다 크다면 가격이 떨어졌다는 뜻이다. 떨어지지 않은 시간은, 현재 인덱스에서 스택의 top의 인덱스를 빼준 값이다. 따라서 answer의 (스택의 top의 인덱스)에 값을 대입해준다. 스택의 top은 이미 가격이 떨어졌기 때문에, 스택 s에서 pop해준다. while문을 통해서 현재 비교하는 prices[i]와 스택의 top을 비교해준다. 

    for(int i=0; i<prices.size(); ++i)
    {
        answer.push_back(0);
        while (!s.empty() && prices[i] < s.top().first)
        {
            answer[s.top().second] = i - s.top().second;
            s.pop();
        }
        s.push(make_pair(prices[i], i));
    }

 

두번째 for문에서는 가격이 끝까지 떨어지지 않은 것들의 시간을 구해준다. 벡터를 0으로 초기화하였기 때문에, answer[i]의 값이 0이면 가격이 끝까지 떨어지지 않았다는 뜻이다. 따라서 prices.size()는 총시간이 되므로 현재 인덱스 i를 빼주고, 1을 더 빼준다.

    for(int i=0; i<prices.size(); ++i)
    {
        if(answer[i] == 0)
            answer[i] = (int)prices.size() - 1 - i;
    }