주식가격

작성일 | In

[프로그래머스] 주식가격

문제 링크

주어진 주식 가격 배열을 0번째 인덱스부터 순차적으로 탐색하면서, 현재 주식가격보다 낮은 가격이 있는지 확인하는 문제이다.
단순히 순차 탐색으로 문제를 풀면, 시간복잡도는 $O(n^2)$이고 n이 최대 100,000이므로 시간초과가 난다.
따라서 주식 가격 배열을 한 번만 순회하는 풀이 방법을 사용해야할 것이라고 예상했고, 문제 풀이 방법으로 스택을 사용했다.

스택은 pair 데이터를 저장할 수 있다. first는 주식 가격, second는 해당 주식 가격의 인덱스이다. 스택에는 아직 가격이 낮아지지 않은 주식 가격들이 저장된다.
기본적으로 주식 가격 배열을 순차적으로 탐색하는데, 현재 인덱스의 가격과 스택의 top을 비교하여 현재 인덱스 가격이 같거나 더 높다면 스택에 저장하고, 그렇지 않다면 스택의 top이 현재 주식 가격보다 같거나 낮아질 때 까지 pop한다. 이 때, pop된 주식 가격들은 가격이 떨어진 시점이 현재 인덱스이므로 그 차를 구해 정답 배열에 저장한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <string>
#include <vector>
#include <stack>
using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    stack<pair<int, int>> stk;

    answer.resize(prices.size(), 0);
    stk.push({0, 0});
    int len = prices.size();
    for(int i=0; i<len; ++i) {
        while(prices[i] < stk.top().first) {
            pair<int, int> top = stk.top();
            stk.pop();
            answer[top.second] = i - top.second;
        }
        stk.push({prices[i], i});
    }

    while(stk.size() != 1) {
        pair<int, int> top = stk.top();
        stk.pop();
        answer[top.second] = len - 1 - top.second;
    }
    
    return answer;
}

int main(void) {
    int n;
    scanf("%d", &n);

    vector<int> prices(n);
    for(int i=0; i<n; ++i)
        scanf("%d", &prices[i]);
    
    solution(prices);
}
0%