[프로그래머스]스택/큐 - 주식가격

문제

풀이

#include <string>
#include <vector>

using namespace std;

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

이중반복문과 벡터를 이용해 풀 수 있었다.

 

 

 

 

---

다른 사람 코드

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

using namespace std;

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

문제의 의도처럼 스택을 이용해서 푼 풀이이다.

스택에 인덱스 값을 넣어 주식의 가격이 떨어지지 않은 시간을 구할 수 있었다.

스택에 활용법에 대해 또 한 번 알아갈 수 있었다.

 

나의 풀이

다른 사람 풀이

스택의 시간 복잡도는 O(N)이고 이중반복문의 시간복잡도는 O(N^2) 이므로

위와 같이 스택을 이용해서 푼 것이 더 효율적이다.