[스택/큐, 난이도 하] 프로그래머즈, 주식가격

이 문제는 맞추고도 당황했다.

prices의 길이는 최대 100000인데 prices의 길이에 대한 이중 반복문을 사용했는데 효율성까지도 만점을 받았다.

그래서 난이도를 '하' 로 정했다. 

뒤의 요소들을 탐색하면서 시간을 계속 더해주되, 주식가격이 현재가격보다 아래가 되는 경우 바로 break를 해줘서 그런 것 같은데, 테스트 케이스들이 최악의 경우 까지는 고려를 안해서 그런 것 같다. 

prices의 길이가 100000이고, 주식 가격이 계속 오르기만 하는 경우에서 최악의 시간 복잡도가 나올 것이다.

 

현재의 주식 가격과 그 다음의 주식 가격의 관계만 신경 쓰면 되므로 이 문제에서 요구하는 것은 스택이라고 볼 수 있다.

벡터와 인덱스 변수만으로도 스택을 흉내낼 수 있기도 하고 벡터를 이용하는 것이 소스 코드도 훨씬 짧기 때문에 벡터로 해결했다. 

 

정확성, 효율성 모두 만점

 

#include <vector>
using namespace std;
vector<int> solution(vector<int> prices) {
    vector<int> answer;
    int survive=0;
    for(int i=0;i<prices.size();i++){
        for(int j=i+1;j<prices.size();j++){
            if(prices[i]>prices[j]) {
                answer.push_back(survive+1);
                break;
            }
            else survive++;
        }
        //끝까지 떨어지지 않는 경우 계산
        if(survive==prices.size()-i-1) answer.push_back(prices.size()-i-1);
        survive=0;
    }
    return answer;
}