프로그래머스 : 스택/큐 주식가격(lv2)

프로그래머스 링크

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

프로그래머스

문제 설명

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

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예 | prices | return

[1, 2, 3, 2, 3]

[4, 3, 1, 1, 0]

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

코드(스택, 큐 사용 x)

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

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    
    // 가격을 미리 얻어놓는다
    // 반복문 조건식에서 size를 얻는거는 비효율
    size_t Size = prices.size();
    
    for(size_t i = 0; i < Size - 1; ++i)
    {
        int SecondTime = 0;     // 시간 변수
        int Price = prices[i];  // i번째의 가격
        
        for(size_t j = i + 1; j < Size; ++j)
        {
            ++SecondTime;   // 매 인덱스에 접근할때마다 1초 증가
            // i번째의 가격보다 작다면 가격이 떨어진것이기 때문에 반복문 중단
            if(Price > prices[j]) 
            {
                break;
            }
        }
        
        // 떨어질때까지의 시간을 정답배열에 넣는다.
        answer.push_back(SecondTime);
    }
    
    // 마지막 인덱스는 무조건 0
    answer.push_back(0);
    
    return answer;
}

정확성 및 효율성

스택, 큐를 사용한 코드

#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])
        {
        	//i가 즉 현재의 시간이고 s.top은 그 당시의 시간
            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;
}

---

우선 이 문제를 풀면서 해결하지 못한 부분은 스택, 큐를 이용해서 풀지 못한 부분이다.

문제의 제목은 스택, 큐를 이용하라고 되어있는데 결국 방법을 떠올리지 못하고 2중포문을 돌려서 해결하였다.

확실히 많은 알고리즘 문제를 풀어봐야 할 거 같다.