프로그래머스 [주식가격] 문제 스택으로 풀기

#1 개요

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

프로그래머스

 

큐와 스택 문제 카테고리에 있는 프로그래머스 문제.

 

이중 for문을 통한 O(n^2) 풀이법 밖에 떠오르지 않아 스택으로 푸는 방법이 뭔지 찾아 헤메다 정리하게 되었다.

 

#2 풀이

간단하게 내 이해를 요약하자면, Stack풀이법은 "주식이 아직 떨어지지 않은 시점" 들을 stack내부에 저장하는 방법을 사용한다.

 

"어? 그럼 Stack의 바닥에 깔린 애는 주식이 떨어졌는데, Stack의 위에 있는 애의 주식은 안 떨어졌으면 어떡하나요? 바닥에 깔린 시점을 뺄수가 없는데요?"

 

즉, 위 그림과 같은 문제가 생길 수 있지 않을까 생각했었는데, 그림에서 보면 알 수 있다시피 이는 불가능하다.

왜냐하면 이렇게 되면 Stack내부에서 이미 2초가 가격이 1초에 비해서 떨어져 있기 때문이다.

 

알고리즘을 제대로 짜면 이미 2초 데이터 '1'을 Stack에 집어넣었을 때, 1초 데이터 '3'이 빠져나와야하는 것이다.

 

정리하자면, 이 문제에서 Stack구조를 사용할 수 있는 이유는 매시점 Stack에 값을 저장하며, 이때 가격을 역행하는 데이터를 넣어야하는 순간, Stack에 저장되어 있는 데이터들이 가격에 역행하지 않을 때까지 pop해버린다는 것이다.

 

따라서 위의 옳지 않은 의문에 해당하는 그림은 다음과 같은 순으로 변경된다.

 

#3 코드

#include <iostream>
#include <string>
#include <vector>
#include <stack>

using namespace std;

struct info {
    int price;
    int sec;
};

//한 주식이 초단위. 바로 다음 index에 값이 떨어져도 1초. 즉 자기 자신을 1초로 셈.
vector<int> solution(vector<int> prices) {
    vector<int> answer;

    //어느 시점에 들어갔는지도 함께 저장해둬야 끝까지 빠지지 않은 애들의 시간을 계산해주기 쉽다.
    stack<info> s;

    answer = vector<int>(prices.size(), -1);

    for (int i = 0; i < prices.size(); i++) {
        if (s.empty()) {
            s.push( {prices[i], i} );
        }
        else {
            //stack이 다 비거나, 가격이 작거나 같을 때까지 pop
            while (!s.empty() && s.top().price > prices[i]) {
                //주식 가격이 오른 sec = 현재 시점(i) - stack에 저장되어 있는 시점
                int temp = i - s.top().sec;
                answer[s.top().sec] = temp;

                s.pop();
            }
            s.push({ prices[i], i });
        }
    }

    int temp;

    while (!s.empty()) {
        temp = prices.size() - 1 - s.top().sec;
        answer[s.top().sec] = temp;
        s.pop();
    }

    return answer;
}

 

 

#4 여담

이중 for문이지만 완전히 처음부터 도는 for문이 아니어서 그런지 stack을 쓴것과 비슷한 속도가 나왔다.