스택/큐 - 주식가격

https://www.welcomekakao.com/learn/courses/30/lessons/42584

 

사실 문제이해가 제일 오래걸렸다... 1초, 2초 시점은 이해가 되지만 3초 시점이 왜 1이지..?

국어능력도 필요한 문제인 것 같다. 어쨌든 위 문제의 풀이방법은 아래와 같다.

 

1. 2중 for 문 중 첫번째 for 문은 처음부터 끝까지 주식의 가격을 순회한다.

2. 두번째 for 문에서 다음 날 가격 끝까지 주식의 가격을 순회한다.

3. 두번째 for 문에서 가격하락이 발생한 날을 찾는다. 만약 가격이 하락했다면 두 주식의 index 차이를 계산하여 정답에 push 하고, 가격하락이 되었다는 flag 를 true 로 설정해준다.

4. 3번 case 에 해당되지 않는다면(주식이 하락하지 않았다면), 마지막 날까지 변동이 없는 것이므로 입력으로 주어진 prices 의 크기( prices.size() )에서 현재 비교대상이 되었던 주식의 index( i ) 의 차이를 구한다. 추가적으로 -1 을 해주는 이유는 배열의 특성 상 index 는 0부터 시작하기 때문이다.

#include <string>
#include <vector>
 
using namespace std;
 
vector<int> solution(vector<int> prices) {
    vector<int> answer;
    
    for (int i = 0; i < prices.size(); ++i) {
        bool decrease = false;
        for (int j = i + 1; j < prices.size(); ++j) {
            if (prices[j] < prices[i]) {
                answer.push_back(j - i);
                decrease = true;
                break;
            }
        }
        if (!decrease) answer.push_back(prices.size() - i - 1);
    }
    return answer;
}