주식가격(미흡)

https://school.programmers.co.kr/learn/courses/30/lessons/42584#

2023-11-14: 다른 사람의 풀이를 해석해 풀었지만 미흡하다. 나중에 다시 풀어볼 문제.

아직 미해결. 진짜 코테라면 틀린 문제다. 30분이 지났는데 어떻게 고칠지 생각이 들지 않아 일단 멈췄다. 시간 재지 않고 다시 풀어보자.

구현 아이디어 10분 구현 20분

틀린 풀이

틀린 풀이지만 내 생각은 이랬다.

1. 스택에 배열 값을 전부 넣는다.
2. 뒤에서부터 꺼내면서 꺼낸 값 <= 지금까지 꺼낸 값 중 최솟값이라면 지금 꺼낸 값은 마지막까지 가격이 떨어지지 않는다.
3. 꺼낸 값 > 지금까지 꺼낸 값 중 최솟값이라면 꺼낸 값은 최솟값의 시간까지만 가격이 떨어지지 않는다.

이런 구현을 했는데 틀렸다.
반례는 [5, 4, 3, 2, 1]일 때 정답은 [1, 1, 1, 1, 0]이지만 출력은 [4, 3, 2, 1, 0]이다.
최솟값인 1과 1의 시간인 0초가 갱신되지 않기 때문이다. 틀린 풀이를 첨부한 뒤에 다시 풀어보자.

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

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    
    stack<int> s1;
    for(int i = 0; i < prices.size(); ++i)
    {
        s1.push(prices[i]);
    }
    
    int cur_sec = 0, mini = 2147000000, mini_sec = 0;
    while(!s1.empty())
    {
        // 하나 꺼냄.
        int price = s1.top();
        s1.pop();
        
        // 지금까지 나온 최소 가격보다 price가 같거나 작다면 끝까지 가격이 떨어지지 않음.
        if(mini >= price)
        {
            mini = price;
            mini_sec = cur_sec;
            answer.push_back(cur_sec);
        }
        else
        {
            answer.push_back(cur_sec - mini_sec);
        }
        
        ++cur_sec;
    }
    
    reverse(answer.begin(), answer.end());
    
    return answer;
}

---

틀린 풀이

이 풀이는 [5, 4, 3, 2, 1]에 대해서는 해결 했지만 틀렸다. 반례를 찾아보자.

반례를 찾았다.
[1, 3, 5, 7, 9, 4, 5, 2, 1, 0]을 입력할 경우 [9, 6, 3, 2, 1, 2, 1, 1, 1, 0]가 나와야 한다. 하지만 [9, 8, 3, 2, 1, 2, 1, 1, 1, 0]가 출력된다. 구현 아이디어를 아예 다시 생각하자.

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

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    
    stack<int> s1;
    for(int i = 0; i < prices.size(); ++i)
    {
        s1.push(prices[i]);
    }
    
    int cur_sec = 0, mini = 2147000000, mini_sec = 0;
    while(!s1.empty())
    {
        // 하나 꺼냄.
        int price = s1.top();
        s1.pop();
        
        // 지금까지 나온 최소 가격보다 price가 같거나 작다면 끝까지 가격이 떨어지지 않음.
        if(mini >= price)
        {
            mini = price;
            mini_sec = cur_sec;
            answer.push_back(cur_sec);
        }
        else
        {
            // 이 경우에 top을 슬쩍 보고 top이 더 크다면 mini 값과 mini_sec 값을 갱신하자.
            bool change = false;
            if(!s1.empty())
            {
                int nx_price = s1.top();
                if(nx_price > price)
                {
                    change = true;
                }
            }
            
            answer.push_back(cur_sec - mini_sec);
            
            if(change)
            {
                mini = price;
                mini_sec = cur_sec;
            }
        }
        
        ++cur_sec;
    }
    
    reverse(answer.begin(), answer.end());
    
    return answer;
}

---

풀이(이중 for문)

이중 for문으로 풀었다. 효율성 통과는 했지만 스택/큐 카테고리에서 이중 for문이라니... 불만족. 스택으로 풀고야 만다.

#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 = 0;
        for(int j = i + 1; j < prices.size(); ++j)
        {
            time++;
            if(prices[i] > prices[j])
            {
                break;
            }
        }
        
        answer.push_back(time);
    }
    
    return answer;
}

---

풀이(스택)

다른 사람의 풀이를 봤다. 풀이를 읽었지만 바로 이해가 안됐다. 시간이 지나면 다시 풀 문제이다.

1. i를 돌며 prices를 확인한다.
2. prices < prices[stack.top()]라면 answer[stack.top()]은 갱신해야 한다.
3. 그게 아니라면 i를 stack에 push 한다.
4. 마지막에 stack에 남은 값들은 끝까지 변화가 없는 가격들이다. prices.size() - 1 - stack.top()을 통해 answer를 갱신한다.

#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> sec;
    
    for(int i = 0; i < N; ++i)
    {
        while(!sec.empty() && prices[i] < prices[sec.top()])
        {
            answer[sec.top()] = i - sec.top();
            sec.pop();
        }
        sec.push(i);
    }
    
    while(!sec.empty())
    {
        answer[sec.top()] = N - 1 - sec.top();
        sec.pop();
    }
    
    return answer;
}