프로그래머스 | 주식가격

<문제>

 

문제 자체가 별로 어렵지는 않아서 쉽게 풀 수 있을 줄 알았음.

#include <string>
#include <vector>

using namespace std;

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

 

실제로도 이중 for 문으로 쉽게 풀긴 했지만

이러면 거의 O(N^2)만큼 시간복잡도가 걸려서

좀 더 쉽게 푸는 방법이 있을 것 같다

 

조금 찾아보니까 stack으로 풀 수 있다고 한다

진짜 완전 개쩌는 풀이도 있는데

우선 내 힘으로 풀어보고

개쩌는 풀이 반영해보자!

---

내가 풀어보는 풀이

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

vector<int> solution(vector<int> p) {
    vector<int> ans(p.size());
    stack <pair<int, int>> s;
    // pair 써서 인덱스, 값 으로 활용
    
    for(int i = 0; i<p.size(); ++i){
    	//s에 뭐가 있고, 맨 위 값의 가격이 현재가보다 높으면 while입장
        while(!s.empty() && s.top().second > p[i]){
            ans[s.top().first] = i-s.top().first;
            //지금 인덱스 - s.top의 인덱스
            s.pop();
        }
        s.push({i,p[i]});
    }
    
    // 끝까지 다 돌고 나면 남은애들은 가격 안떨어진거니까 맨 끝의 값 기준으로 초 세기
    while(!s.empty()){
        ans[s.top().first] = p.size()-s.top().first-1;
        s.pop();
    }
    return ans;
}

 

---

개쩌는 풀이

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size());   // 결과를 저장할 벡터
    stack<int> s;                        // 인덱스를 저장하는 스택

    for (int i = 0; i < prices.size(); i++) {
        // 현재 가격(prices[i])보다 큰 가격을 가진 과거 인덱스들을 처리
        while (!s.empty() && prices[s.top()] > prices[i]) {
            answer[s.top()] = i - s.top(); // 가격이 떨어진 순간까지의 시간 계산
            s.pop();
        }
        s.push(i); // 현재 인덱스 push
    }

    // 끝까지 가격이 안 떨어진 경우 처리
    while (!s.empty()) {
        answer[s.top()] = prices.size() - s.top() - 1;
        s.pop();
    }
    return answer;
}

얘는 인덱스 기준으로 가지고 노는거

내꺼랑 비슷한 방법인데 나는 pair을 썼는데 이사람은 인덱스만 써서

가격이 안떨어지는 애들은 stack에 인덱스로 넣어두고

그 인덱스를 p 에서 비교하면서 계산하니까 공간복잡도가 훨씬 낮아진다

 

대박적

 

방법	시간복잡도	공간복잡도
이중 for문	O(N²)	O(1)	구현은 쉽지만 데이터가 크면 매우 느림
스택	O(N)	O(N)	빠르고 효율적, 실무에서 선호