문제
문제 해결 전략
처음에 내가 난독이 있는건지 문제를 해석하는것 조차 헷갈렸다..
우선 인덱스를 넘겨주는 기준이 되는 포문 하나와 기준의 뒤에 남은 인덱스 중에서 기준보다 작은 값을 가진다면 내림차순으로 바뀌는 타이밍에 포문을 빠져나오는 방식으로 코드를 짜봤다.
코드1
vector<int> solution(vector<int> prices){
int l = prices.size();
vector<int> answer(l, 0);
for(int i = 0;i < l;i++){
for(int j = i+1;j < l;j++){
answer[i] += 1;
if(prices[i] > prices[j]) break;
}
}
return answer;
}위 코드는 그냥 쉽게 현재 인덱스의 위치에서 바로 다음 인덱스 부터 끝까지 유지되는 초수(인덱스 j)를 계속 해서 더해주고 내림차순으로 바뀌는 순간 loop를 빠져나오는 방식이다.
시간복잡도가 O(n^2)인 코드이다.
다른사람 코드
사실 스택을 사용해서 풀이를 해도 될것 같다는 생각을 하긴 했지만 막상 스택 container 자체를 쓰는게 오랜만이라 귀찮기도 했고,,, 테케를 통과하고나니 다른 생각이 들지 않았던것 같다.
스택을 이용한 풀이
Test Case
1, 2, 3, 2, 3
0, 1, 2, 3, 4
i = 0
s.push(0);
stack = 0
i = 1
prices[0] > prices[1] x
s.push(1);
stack = 1 0
i = 2
s.top = 1
price[1] > price[2]
s.push(2);
stack = 2 1 0
i = 3
s.top = 2
answer[2] = 3-2;
stack = 3 1 0
i = 4
s.top = 3
stack = 4 3 1 0
마지막 while
answer[4] = 5 - 4 - 1;
stack = 3 1 0
answer[3] = 5 - 3 - 1;
stack = 1 0
answer[1] = 5 - 1 - 1;
stack = 0
answer[0] = 5 - 0 - 1;
answer = [4, 3, 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());
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;
}결론적으로 보면 증가하는 인덱스들은 전부 stack에 넣어둬서 나중에 계산해주고 감소하는 인덱스만 for문에서 찾아서 while문에서 미리 answer 값을 계산해주는 방식이다.
