[プログラマー]株価(C++)

📌 リファレンス
引き渡しアルゴリズム研究に関わる問題は19週目からBellogに記録される(18週前に復習してアップロードする予定)🤗) 他の個人が回答した基準やプログラマの質問は、自分が意味があると思っている部分だけをフィルタリングしてBellogに記録します.Bellogにアップロードされていない他の質問やコードを知りたい場合は、次のGithubでさらに確認できます.👀 ご来店ありがとうございます🙏
💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers

エンコードテスト高得点Kit>スタック/キュー

株価|問題ショートカット

回答（2022年1月20日WED）💻)

🤔 サダム+イタリア草のコア?!

これはスタック/キュータイプに分類される問題です.
スタックを活用して解きほぐそうとしたが思い出せなかった
だから私はそのままの感じで、二重for文を書いて、それから回りました.
O(N^2)複雑度なので心配…幸い時間を超えなかった(?)
cf)本当に不思議で、二重for文のコードを書くのはスタックのコードを書くのと同じ効率です.
特に思いつかない方法がなければ、直感的に問題を解決するのも悪いことではありません!

🔽 冗長for文コード効率テスト結果

🔽 スタックコード効率テスト結果

今日の私の解答はあまりにも直観的で、何の説明もありません.
👇 スタックでロックを解除する方法を知りたいので、グーグル霊の後でコードを修正しました.

Googleで入手したTip

価格の並び値、つまり株の価格をスタックに入れてみました.
コアは、価格配列インデックス、すなわち株価の時点(秒単位)をスタックに配置することです.
👉 価格の面では.
i)価格が下がっていない場合は、ポイントをスタックに押してください.
ii)価格が下落した場合、現在の時点(i)-
答えベクトルの対応する時点インデックスに格納され、その時点がポップアップされます.
👉 prices配列は終了し、スタックが空でない場合、
これは、スタックに問題が発生するまで価格が下落しなかったことを意味します.
前の時点(prices.size(-1)からその時点(timestack.top())の値を減算します.
答えベクトルの対応する時点インデックスに格納され、ポップアップされます.

🔽 冗長for文コード（C++）

#include <string>
#include <vector>

using namespace std;

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

🔽 スタックのコードを使用(C++)

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

using namespace std;

vector<int> solution(vector<int> prices) {
    int N = prices.size();
    vector<int> answer(N);
    stack<int> timeStack;

    for (int i=0; i<N; i++) {
        while (!timeStack.empty() && prices[i] < prices[timeStack.top()]) { // 가격이 떨어진 경우
            answer[timeStack.top()] = i-timeStack.top(); // 떨어지지 않은 기간 계산 (현재 시점 - 해당 시점)
            timeStack.pop(); // 해당 시점 pop
        }
        timeStack.push(i); // 현재 시점 push
    }

    while(!timeStack.empty()) { // 끝까지 가격이 떨어지지 않은 나머지 경우들 처리
        answer[timeStack.top()] = (N-1) - timeStack.top(); // 떨어지지 않은 기간 계산 (종료 시점 - 해당 시점)
        timeStack.pop(); // 처리 완료된 해당 시점 pop
    }

    return answer;
}