[C++]주식 가격

첫 풀이

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;

    for(int i = 0; i < prices.size(); i++) {
        if(i == prices.size() - 1) {    //마지막 값은 0
            answer.push_back(0);
            continue;
        }

        for(int j = i+1; j < prices.size(); j++) {
            if(prices[i] > prices[j] || j == prices.size()-1) { //값이 떨어짐
                answer.push_back(j-i);
                break;
            }

            if(j == prices.size()-1) {  //마지막값과 비교해도 통과라면
                answer.push_back(j-i);
                break;
            }
        }
    }
    return answer;
}

이 문제 모 기업 2번문제였는데... 사실상 똑같음. 신기하네 ㅎㅎ;

첫 풀이는 단순한 이중반복문으로 했다.

신기하게도 효율성 테스트를 통과함. O(n^2)인데 이거 왜 효율성 통과함?(진심몰룸)

그 기업 코테는 이렇게 이중반복문을 쓴 경우 효율성을 통과하지 못하게 테스트가 세팅되어있었다.

두번째 풀이

스택을 활용했다.

#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;
}

코드 하나 토씨틀리지 않게 같은 방식이었는데 나는 테케1만 통과하고 나머지 다 틀리던데 뭔 문젠지 모르겠음.

대신 통과되는 다른 코드 추가.

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

using namespace std;

vector<int> solution(vector<int> prices) {
    const int SIZE = prices.size();
    vector<int> answer(SIZE);
    stack<int> s;
    
    for(int i = 0; i < SIZE; i++) {
        if(!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;
}

요게 내 코드인데 내껀 통과가 안댐 먼차이냐능

의외로 효율성 테스트의 시간차이는 없다. 테케가 이상한게분명함