[고득점Kit][스택] 주식 가격 ⭐⭐

Date: 2020.07.27 Updated: 2021.05.21

카테고리: Programmers

[스택/큐] 주식 가격

난이도 ⭐⭐

문제

내 풀이

첫 번째 풀이

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

이 풀이의 시간 복잡도는 최악의 경우 \(O(N^2)\) 이다.

예시로 설명
- prices[0] = 1 초 (i = 0)와 2 초, 3 초, 2 처, 3 초를 각각 비교해서 가격이 떨어졌는지를 알아봐야 한다.
  - 비교할 때마다 무조건 count를 1씩 더한다.
  - 1 <= 2 니까 비교를 계속 이어간다. 1 <= 3 니까 비교를 계속 이어간다. 1 <= 2 니까 비교를 계속 이어간다. 1 <= 3 니까 비교를 계속 이어간다.
    - 총 count = 4
    - answer[0] = 4 가 들어가게 된다.
- prices[2] = 3 초 (i = 2)와 3 초, 2 초, 3 초를 각각 비교해서 가격이 떨어졌는지를 알아봐야 한다.
  - 3 > 2 니까 가격이 떨어진 것을 알게 되었으므로 3 초에 대해서는 더 이상 비교를 하지 않는다.
  - 그러나 바로 3 > 2 가 되었더라도 2 로 떨어지기까지의 0 ~ 1 초 동안은 가격이 떨어지지 않은 것으로 보기 때문에 count = 1 이 된다.
    - 즉 가격이 떨어지든 아니든 비교할 때마다 count는 계속 1씩 증가시켜 주어야 함
- 마지막 원소는 조건에 안맞아 두번째 j for문을 돌지 않게 되기 때문에 자연스럽게 count = 0 으로 들어간다.

두 번째 풀이 (stack 사용)

#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[i] < prices[s.top()]){
            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;
}

이 풀이의 시간 복잡도는 언제나 \(O(N)\) 이다.

예를 들어 스택에 [1,2,3,4,5] 주식 가격이 들어있는 상태에서 (top은 5인 상태) 주식가격 2 원의 차례(인덱스)가 된다면! 스택 안에 들어있는 3, 4, 5 원은 가격이 떨어지게 되는 것이다. 차례로 2 원보다 큰 스택 안의 가격들을 pop 시키고 인덱스의 차이를 answer 원소로 저장하면 된다.
- 스택 안의 top에 위치한 주식 가격보다 price[i] 현재 검사 중인 주식 가격이 더 작다면 top 주식 가격을 pop 한다.
  - 스택 안에 저장되어 있는 가격들 중에 price[i] 가격으로 ‘가격이 떨어졌다.’고 판단될 수 있는 모든 가격들을 pop 시킨다.
- 스택 안의 top에 위치한 주식 가격보다 price[i] 현재 검사 중인 주식 가격이 더 크거나 같다면 가격이 떨어진 것이 아니기 때문에 나중에 가격이 떨어질 것을 대비해 스택에 push 해둔다.
모든 주식 가격의 순회를 마친 후에도 스택 안에 pop 되지 못하고 남아있는 원소들은 한 번도 주식 가격이 떨어진적이 없는 원소들이나 마찬가지다! 따라서 마지막으로 이 원소들에 대한 처리도 해준다.

스택으로 풀면 시간복잡도가 O(n) 인 이유

스택을 사용하면 선형 시간 O(N) 으로 접근할 수 있다.

시간 복잡도는 O(N) + O(N) = O(2N) = O(N) 이 된다.
- 모든 주식 가격은 한 번씩 push 된다. 👉 O(N)
- 모든 주식 가격은 한 번씩 pop 된다. 👉 O(N)

여담..

첫 번째 풀이는 최악의 경우의 시간복잡도는 \(O(N^2)\) 이 된다.
반면 두 번째 풀이는 시간복잡도가 \(O(N)\) 이 된다.

그런데 첫 번째 풀이는 효율성 테스트를 별 문제 없이 통과했으며 두 풀이의 연산 시간도 거의 차이가 없었다.. 왜지..? 😮 십만 개에 달하는 큰 주식가격 입력들이 모두 떨어지는 경우가 단 하나도 없는 테스트 케이스라면 두 풀이의 시간이 확실히 차이날 듯 한데.. 내가 무언갈 놓치고 있는 것인지 테스트 케이스가 빈약한건지 모르겠다. 궁금하다!

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️