[Level2.] 주식가격 C++

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

풀이

 

사실 좀 놀랐던 것은... 이 정도 문제가 레벨2라고...?

 

백준은 난이도가 세분화되어있어서 난이도 파악이 쉬웠는데,

프로그래머스는 조금 큰 단위로 자르다보니 난이도가 같아도 실제 느끼는 난이도는 천차만별인것 같네요.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    
    for(int i=0; i<prices.size()-1; i++){
        answer.push_back(0);
        for(int j=i+1; j<prices.size(); j++){
            if(prices[i] <= prices[j]){
                answer[i]++;
            }
            else{
                answer[i]++; // 끊기더라도 1초는 버틴것으로 인정
                break;
            }
        }
    }
    answer.push_back(0); //마지막 요소의 시간은 0
    return answer;
}

O(n^2)으로 해결했습니다.

 

사실 더  효율적인 방법이 가능해보이네요.