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

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

 

각 인덱스에 대하여 처음으로 가격이 떨어지는 인덱스를 구해 리턴하는 문제이다.

가장 먼저 이중 for문을 사용한 풀이가 떠오른다.

 

vector<int> solution(vector<int> prices) {
    
    vector<int> v(prices.size(), 0);
    
    for (int i=0; i<prices.size(); i++) {
        int cnt = 0;
        for (int j=i+1; j<prices.size(); j++) {
            cnt++;
            if (prices[i] > prices[j]) break;
        }
        v[i] = cnt;
    }
    return v;
}

 

각 인덱스마다 prices 배열을 순회하면 처음으로 가격이 떨어지는 위치를 구할 수 있는데, 해당 방법의 시간복잡도는 O(N^2)이다

놀랍게도 이 방법은 정답으로 처리된다. 입력 값이 100000이므로 O(N^2)은 TLE가 나야하는데, 아마 테스트케이스가 약한 듯 싶다.

 

공부하는 입장이므로, 조금 더 효율적인 풀이 방법을 생각해보자.

일단, 문제를 해결하기 위해 알아야 할 사실이 있다.

수 a에 대하여 처음으로 가격이 떨어지는 수가 b라면 그 사이에 있는 수들 역시 가격이 떨어지는 수로 b를 갖는다.

a 이후 처음으로 등장한 작은 수가 b라면, 그 사이의 수들은 a보다 크거나 같고, 해당 수들도 b를 처음으로 등장한 작은 수로 갖는다.

이 말인 즉슨, b를 가격이 떨어지는 첫번째 수로 갖는 수들은 연속해서 존재한다.

 

따라서 스택을 사용하면 b를 떨어지는 수로 갖는 연속적인 수들을 꺼낼 수 있다.

prices를 순회하면서 prices[i]를 떨어지는 수로 갖는 수들을 스택에서 꺼낸다.

prices[i]보다 큰 수들을 연속적으로 꺼내고, i와 해당 인덱스의 차이를 저장한다.

 

prices를 모두 순회하고도 스택에 남아있는 수들은 떨어지는 수를 찾지 못한 수들이므로 배열의 가장 끝 인덱스(prices.size()-1)에서 각 인덱스의 차이를 구해 최종 배열을 리턴하면 정답이다.

 

 

코드

 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int>;

#define X first
#define Y second

vector<int> solution(vector<int> prices) {
    
    stack<ii> st;
    vector<int> ans(prices.size(), 0);
    
    for (int i=0; i<prices.size(); i++) {   
        while (!st.empty() &&  st.top().Y > prices[i]) { //prices[i]를 떨어지는 수로 갖는 인덱스를 모두 찾기
            ans[st.top().X] = i-st.top().X;
            st.pop();
        }
        st.push({i, prices[i]});
    }
    
    while (!st.empty()) { //떨어지는 수가 없을 때 가장 끝 인덱스까지의 거리 구하기
        ans[st.top().X] = prices.size()-1-st.top().X;
        st.pop();
    }
    return ans;
}