프로그래머스 lv 2. 42584 c++ 주식가격

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

#include <bits/stdc++.h>

using namespace std;

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

이 문제가 제시되어 있는 부분은, 스택/큐 부분이라 그걸 이용해서 구현을 해도 되는 문제로 보여지고, 오히려 그게 더 효율성 부분에서는 시간단축이 있을수도 있겠으나, 가장 먼저 떠오르는 방식은 위와 같은 형태의 이중for문을 이용하는 풀이었고, 위와 같이 구현하였다. 

 

이게 내가 위에 구현한 이중 for문을 이용한 방법의 효율성 테스트 결과인데, 확실하게 시간이 많이 걸리는 편이다. 

 

스택/큐 카테고리에 맞게, 해당 방식을 이용한 풀이에 대해서 찾아보고, 그리고 그런 풀이를 했을때의 효율성에 대해서도 언급해놓은 블로그 글을 발견할 수 있어서 첨부해보겠다. 

https://mungto.tistory.com/6

주식가격 문제풀이(C++, 스택/큐)[프로그래머스]

이분의 블로그 풀이에 효율성 스크린샷까지 찍어놓으셔서 비교를 잘 해볼 수 있었다. 

 

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
vector<int> solution(vector<int> prices) {
    int size = prices.size();
    vector<int> answer(size);
    stack<int> st;
    for (int i = 0; i < size; i++) {
        //스택이 비어있지않고 스택마지막 값이 현재값보다 크다면
        //-> 가격이 떨어졌다면
        while (!st.empty() && prices[st.top()] > prices[i]) {
            //가격이 떨어졌으므로 i - 스택 마지막값 대입
            answer[st.top()] = i - st.top();
            //값제거
            st.pop();
            //반복문인 이유: 가격이 같은값이 유지되었을경우
            //현재값보다 계속작으므로 1개차이씩 넣어주기 위해서다.
        }
        //현재 인덱스를 스택에 넣기
        st.push(i);
    }
    //스택이 빌때까지 반복
    while (!st.empty()) {
        //위에서 특정위치에 이미값을 넣었으므로 pushback이나 insert로하면 안된다.
        //뒤에서부터 넣어야하므로 size-1 에서 top값을 빼준다.
        answer[st.top()] = size - st.top() - 1;
        st.pop();
    }
    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]){
            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;
}

결국 이 코드의 경우도 위에 언급한 블로그에 나온 형태와 동일하다. 

이때에 중요한건, 자기보다 작은 값을 만나서 걸러질때의 경우 싹 걸러내주는 연산이 첫번째 for 문 내부에 처리를 해주고,

그리고 나서는 그 바깥에 while(!s.empty()){ } 내부에서는 그런식으로 걸러내지 못하고 자기보다 작은 값이 없어서 완전 끝까지 도달해야

하는 녀석들에 대한 값을 answer에 넣어주는 연산이 나누어져 있다는 것이다. 

이때에 "answer[s.top()]=" 형태로 코드를 작성해서 벡터의 원소에 값을 입힐때 연속적으로 값을 입혀나가는 형태가 아니라는걸

잘 이해해야 한다. 그게 이해가 잘 안되니까 2중 for문을 활용한 형태로 연속적으로 문제를 해결하는 풀이가 바로 생각이 나니까 그렇게 문제를 푸는데, 위와 같이 answer 벡터에 answer[s.top()] 형태로 접근해야 stack을 활용한 풀이를 떠올려서 stack을 사용해서 

연산속도를 확 줄일 수 있다.