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

풀이

가격이 떨어지지 않은 기간을 고르면 되는 문제였다.

2중 for문을 사용해 가격이 떨어지는 순간까지 초를 세서 answer에 넣어주었다. 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    int cnt=0;
    for(int i = 0 ;i<prices.size(); i++){
        cnt=0;
        for(int j=i+1;j<prices.size();j++){
            cnt++;
            if(prices[i]>prices[j])
                break;

        }
        answer.push_back(cnt);
    }
    return answer;
}

 

다른 사람 풀이

스택을 이용한 풀이다  시간 복잡도가 O(n) 이다.

for문을 돌면서
스택에 가격들의 인덱스를 넣는다.
스택에 쌓인 가격(인덱스)들과 비교하여 가격이 떨어졌다면 스택에 쌓인 이전 가격들의 초를 계산해서 answer에 넣어준다.

 while(!s.empty()&&prices[s.top()]>prices[i]){
            answer[s.top()] = i-s.top();
            s.pop();
        }

 

for문이 끝났을때 스택에 가격의 인덱스가 남아있다면 한번도 가격이 떨어지지 않았다는 뜻으므로 가격을 계산해서 넣어준다. 

while(!s.empty()){
        answer[s.top()] = size-s.top()-1;
        s.pop();
    }