[알고리즘] 프로그래머스_주식가격

1. 문제 분석

• 뒤에 가격이 앞에 가격보다 작으면 시간차이를 기록한다.
• 마지막까지 가격이 떨어지지 않으면 끝-해당 위치(시간)를 기록한다.

2. 문제 풀이 과정(삽질)

• 처음에는 완전 탐색을 생각했다. 순차적으로 보면서 앞에 있는 모든 값들과 비교해 큰 값이 있으면 기록하는 식이다.
• 너무 비효율 적이라 스택을 사용하기로 했다.
• 처음에는 2차원 벡터에 vector[값][위치]를 나타내면서, 이미 탐색했나를 판단할까 생각하고, 자신보다 뒤에 있으면서 작은 값을 어떻게 찾을까 생각했다.

3. 문제 해결

• 위처럼 고민하다가 증가하는 추세에서 떨어질 때마다 앞의 값들 중 큰 값의 답을 기록해주는 방식이 생각났고, 이어서 어짜피 이전 값들은 점점 증가하는 형태여서 뒤에 값이 앞에 값보다 크거나 같았다.
• 따라서 스택에 {값, index}를 기록하다가 스택의 top보다 작은 값이 나타나면 하나씩 pop하면서 기록해주면 깔끔하게 큰값은 삭제되고, 작거나 같은 값들은 남아서 다음 처리가 가능했다.
• 마지막으로 끝까지 스택에 남아있는 값들은 입력 SIZE - index로 처리해 마무리를 했다.

4. 코드

• 수정을 하면 가독성이 좋아 보일 것 같다.

#include <string>
#include <vector>
#include <utility>

using namespace std;

vector<int> solution(vector<int> prices) {
    int state = 0;
    pair<int, int> back;
    vector<pair<int, int>> stack;
    
    vector<int> answer(prices.size(), 0);
    
    for(int i = 0; i < prices.size(); i++)
    {
        int now = prices[i];
        if(!stack.empty())
            back = stack.back();
        
        if(stack.empty() || now >= back.first)
        {
            stack.push_back({now, i});
            continue;
        }
        
        while(now < back.first)
        {
            answer[back.second] = i - back.second;
            stack.pop_back();
            if(stack.empty())
                break;
            back = stack.back();
        }
        stack.push_back({now, i});
    }
    
    while(!stack.empty())
    {
        back = stack.back();
        answer[back.second] = prices.size() - 1 - back.second;
        stack.pop_back();
    }
    return answer;
}