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

문제  : Level2 주식가격

[ 문제 출처 ]  https://programmers.co.kr/learn/courses/30/lessons/42584

 

 

[ 문제 풀이 ] 

 

내가 이 문제를 처음 봤을 땐 어디서 풀어 본 문제 같은데?라는 생각을 했다

비슷한 문제를 풀어 봤기에 어렵지 않게 풀 수 있었다

찾아보니 BOJ에서 오큰수 문제이고 풀이 방식도 조금만 다를 뿐 매우 유사하다.

[문제 출처 ] : https://www.acmicpc.net/problem/17298

 

프로그래머스에는 문제의 분류로 스택을 사용함을 지시하였지만 

BOJ 문제에서는 이를 모르고  스택을 사용하지 않을 경우 "시간 초과"가 나지 않을까 싶다..

(물론 스택사용 외에도 다른 풀이가 존재 할 수 있다!)

 

만약 이 문제를 처음 접하고 스택의 활용을 몰랐더라면 

아마도 풀이를 생각해 내기엔 조금은 어렵지 않을까 싶다 내 기억엔  BOJ에서 유사 문제를 풀 때, 

문제풀이의 핵심이 스택의 활용이라는 것을  알고 나서도 한참 동안이나 문제를 못 풀었던 것 같다..

 

 

문제에서 무엇을 요구하는지 알아보자 : 

가격이 떨어지지 않은 기간은 몇 초인지 구하라고 문제에서 요구한다

처음엔 무슨 소리인가 생각을 했지만 예제 입력과 결과를 보고서 대충은 이해할 수 있었다

 

예제 입력을 보자

 

index = 0 인 경우

주식 가격 : 1  "시간이 지나면서 언제 떨어 는가 "를 구하면 된다!  이 말을 조금 더 풀어쓰면

1이라는 숫자보다 앞 칸에 작은 값이 존재해?  존재한다면 몇 칸 앞에 있니?라는 것을 물어보는 것이다 

하지만 1이라는 가격은 시간이 지나도 떨어지지 않으므로 배열의 길이인 : 5초동안은 떨어 지지 않음을

보장할 수 있다 따라서 answer[0] = 5초가 된다. 

 

index = 1 인 경우

마찬가지로 주식 가격 : 2는 시간이 지나도 떨어지지 않는다 따라서 4초( 배열 길이 - (해당 시간) index) 

동안은 주식 가격이 떨어지지 않음을 보장할 수 있다. 따라서 answer[1] = 4초

 

index = 2 인 경우

주식 가격 : 3 은 위에 표에서 볼 수 있듯이 1초 후에  3  --> 2로 떨어지지 않는가!

따라서 answer[2] = 1초 가 된다.

 

 

[해결 방법 1]

 

2중 반복문을 사용하여

각각의 index 마다 앞에 칸을 순회하면서  작은 값을 찾아가면 되는 것 아닌가?

 

[ 소스 코드 ]

vector<int> solution(vector<int> prices) {
    int n = prices.size();
    vector<int> answer(n);
    for (int index = 0; index < n; ++index) {
        for (int j = index + 1; j < n; j++) {
            // 앞을 순회 하면서 prices[index] 보다 작은 값을 찾는다
            if (prices[index] > prices[j]) {    
                answer[index] = j - index;
                break;
            }
        }  
         // 작은 값이 존재 하지 않는 경우 
         // 예제에서 index = 0, index = 1 인 경우이다 배열의 길이에서 - 1 - index 해줌
        if (index != n - 1 && answer[index] == 0) answer[index] = n - 1 - index;
    }
    return answer;
}

이 소스 코드를 짜고 테스트를 해보면서 알게 된 사실이지만 

BOJ에서는 위와 같은 시간 복잡도인  코드를 제출하게 되면 "시간 초과"를 받게 된다.

위와 같은 풀이 O(n^2) 는 안 됨을 보여주려고 했지만 제출 결과 PASS 하게 되어 조금 당황스러웠다

문제(문제의 분류를 통한)에서 요구하는 것도 스택을 사용하는 것인데

테스트 케이스가 매우 빈약한 것이 아닌가 생각된다

 

위의 소스 코드에서 볼 수 있듯이 시간 복잡도는 O(n^2) 이 된다

N  = 10 ^5  인데 말이다

 

하지만 스택을 사용하게 되면

시간 복잡도 : O(n) 으로 주어진 문제를 해결할 수 있다

 

[ 소스 코드 ]

#include <string>
#include <vector>
#include <stack>
using namespace std;
vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());
    stack<int> s;
    s.push(0);
    for (int i = 1; i < prices.size(); i++) {
        while (!s.empty() && prices[s.top()] > prices[i]) {
            answer[s.top()] = i - s.top();
            s.pop();
        }
        s.push(i);
    }
    while (!s.empty()) {
        answer[s.top()] = prices.size() - 1 - s.top();
        s.pop();
    }
    return answer;
}