주식 가격

반복문 사용 풀이

스택/큐 카테고리에 있는 레벨 2 문제이다. 하지만 스택이나 큐를 이용하지 않고 이중 반복문으로 풀고 테스트를 통과했다.
주어진prices[i]의 증가하는 초인 answer[i]를 찾기 위해서

• j=i+1부터 배열의 끝까지 순회 한다.
• 만약 prices[j]<prices[i]라면 증가가 끝난 경우이다.
• i와 j 의 차를 계산하면 이것이 answer[i]이다.

#include <string>
#include <vector>

using namespace std;

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

이중 for문이라서 시간 복잡도가 걱정이 되었지만 안쪽의 for문은 i가 증가함에 따라서 반복 횟수가 줄어들기 때문에 시간 초과의 문제는 없었다.

스택으로 푸는 방법이 궁금해서 다른 사람의 풀이를 찾아 보았다.

스택 사용 풀이

//출처 : https://programmers.co.kr/learn/courses/30/lessons/42584/solution_groups?language=cpp
#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;
}

이전의 값보다 현재 값이 증가하면 스택에 넣고, 감소한다면 answer배열에 기록한다.

배열을 다 돌면 스택에는 증가 하는 인덱스들만 남아 있는데, 하나씩 인덱스부터 배열의 끝 까지 몇개가 있는지 계산해 주면 된다.

그러나 경과 시간은 이중 for문을 사용한 것과 큰 차이가 없다.

구글링을 해보니 많은 사람들이 이 문제를 보고 바로 스택을 써야겠단 생각이 들지 않았다고 한다. 나 역시 굳이 이걸 스택을 써야만 하나? 라는 생각으로 이중 반복문을 썼다. 문제의 분류가 굳이 스택이 아니어도 될 듯 하다..

그리고 프로그래머스의 레벨의 기준이 궁금하다. 같은 레벨 2 문제도 어떤건 아주 간단하게 풀리고 어떤건 복잡하던데 말이지..