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

• [ 장르 ] STACK
• [ 문제 ]

[#42584] 주식가격

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

programmers.co.kr

• My Code

#include <string>
#include <vector>
 
using namespace std;
 
vector<int> solution(vector<int> prices) {
    vector<int> answer;
    int NoDownDuring;		// 해당시점 이후, 주식가격 낮아지기까지 시간체크
    
    answer.assign(prices.size(), 0);		// 주식 수 만큼 정답 벡터 0으로 초기화
    for(int i = 0 ; i < prices.size(); i++)
    {
        NoDownDuring = 0;		// 시간측정은 현 시점부터 0부터 시작
        for(int j = i + 1; j < prices.size(); j++)	
        {
            NoDownDuring++;
            if(prices[i] > prices[j])	// 현 시점 주식에서 뒤에 주식중에 현 시점 주식보다 낮은 시점
                break;
        }
        answer[i] = NoDownDuring;		// 현 시점에서 주식이 낮아지기까지 시간 벡터에 삽입
    }
    return answer;
}

• Another Code

#include <string>
#include <vector>
#include <stack>
 
using namespace std;
 
vector<int> solution(vector<int> prices)
{
    vector<int> answer(prices.size());
    stack<int> s;
    int size = prices.size();
 
    for (int i = 0; i<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()] = size - s.top() - 1;
        s.pop();
    }
 
    return answer;
}

" 알고리즘 풀 때는 성능(주로, 실행시간) 에 대해서 생각을 해보자. "

---

[ CheckPoint ]

• 문제 의도만 파악하면, 문제는 어렵지 않은 문제다.
• 주된 장르는 스택인데, 나는 풀고나니 스택을 안았다. 스택을 써야하는 발상이 나지 않았다.
• 풀고나서보니, 최악의 상황 prices 벡터크기가 10000개이고, 모든 주식 가격이 같다면, 총 실행시간은 O(n^2)시간이 될 수 있다. 이는 굉장히 비효율적일 수 있는데, 이 문제는 이 사항은 수용하기로 했나보다.
• 다른 사람의 코드를 보면, 반복문이 2개가지만, 스택을 잘 활용해서 적어도 O(n^2)의 시간은 걸리지 않다는 것을 알 수있다.