[프로그래머스/C++] 주식가격

[프로그래머스/C++] 주식가격

풀었던 문제를 다시 풀어보자!
풀었던 문제가 맞나싶다

1. 문제

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

2. 제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

3. 풀이

• 현재 시간부터 몇 초 뒤에 가격이 떨어지는지 확인하면 된다.
• 끝까지 가격이 떨어지지 않는다면 prices.size() - 1 - (현재 초)가
  answer에 입력되어야 한다.
• time 변수를 prices.size() - 1 - (현재 초)로 초기화 하고 시작한다.
• 현재 초 뒤로 배열을 탐색하며 가격이 떨어지는 순간을 찾는다.
  • 주식가격이 떨어지면 (떨어지는 초) - (현재 초)를 time 변수에 넣고 내부 반복문을 종료한다.
  • 반복문의 끝까지 갔는데도 가격이 떨어지지 않는다면 time은 처음에 초기화한 값으로 끝난다.
• answer 배열에 time 변수를 삽입한다.
• 위 작업을 배열의 끝까지 반복하고 answer 배열을 return한다.

4. 처음 코드와 달라진 점

• null

5. 코드

#include <string>
#include <vector>

using namespace std;

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

6. 코드(스택 사용)

#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> s;
    
    for (int i = 0; i < n; 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()] = n - s.top() - 1;
        s.pop();
    }
    
    return answer;
}