[C++]프로그래머스 주식가격(스택)

코딩테스트 연습 - 주식가격 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

아무리봐도 문제가 어려운건지 

오랜만에 문제를 풀어서 내 뇌가 굳은건지 ,,

이해를 하는데도 너무 오랜 시간이 걸림.

뇌에 뭐가 있긴 한데 구현은 못하겠음

입력값 〉	[1, 4, 3, 2, 4, 3, 1, 2, 2, 2, 4, 4, 4, 3, 1, 2]
기댓값 〉	[15, 1, 1, 3, 1, 1, 9, 7, 6, 5, 3, 2, 1, 1, 1, 0]

이런 예제를 만들어봤다.

예제는 크게 만들수록 내가 더 정확하게 판단할 수 있는듯하다.

 

#include <string>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size(),0);//이런식으로 벡터를list처럼 크기설정 초기화 ㄱㄴ
    stack<int> temp;
    for(int i = 0; i < prices.size(); i++)
    {
        while(!temp.empty() && prices[temp.top()] > prices[i])
        {
            answer[temp.top()] = i - temp.top(); 
            temp.pop();
        }
        temp.push(i); //없으면 넣어라 (인덱스번호를 넣어야 수월한 참조가 가능..)
    }
    while(!temp.empty())
    {
        answer[temp.top()] = prices.size() - temp.top() - 1; //1 , 4, 7, 16에 해당
        temp.pop();
    }
    return answer;
}

1.우선, answer를 list처럼 index참조하고 싶은데 vector형태였음

인덱스 참조를 하는 vector를 만들고 싶을 때는

vector<int> answer(prices.size(), 0);과 같은 형태로 초기화 할 수 있음을 배움.

 

2.크게 두 가지 동작으로 나뉜다.

2-1. temp라는 stack에 기존 값보다 높은 값이 나올 때마다 push하며 top을 갱신시킴(temp가 비어있을 때도 push)

기존보다 낮은 값이 나오면 다시 기존값보다 높은값이 나와 push할 수 있을 때까지 pop시킴

 

이게 첫번째 동작.

 

2-2. 찌꺼기 제거

위 동작을 실행하고 나면 끝까지 기존값보다 낮은 숫자가 등장하지 않아 stack에 쌓임을 유지하는 아이들이 있다.

이 아이들은 끝까지 처음의 가격이 유지되었다는 뜻이므로 전체 size에서 해당 인덱스를 빼주어야 함.

---

키포인트: 여기 작성한 것처럼 우선 말로 쓰고 이를 구현하는 습관을 다시 들이자.

 

어떤 값이 어떨 때 갱신되어야 하는지 정확히 판단하는 것이 필요할 듯.

 

이러한 문제에서 stack을 이용하려고 하는 경우, stack이 인덱스를 품고 있어야 top이 됐을 때 현재까지 쌓인 list의 마지막 index를 판별하기에 좋음.