주식 가격
1,2,3,2,3….
시간은 오른쪽으로 간다
생각해야 할 것은 ‘떨어지지 않는 시간’ -> 어떤 것을 쓰던 오름차순(같은거 허용)으로 쌓자
오름차순이라면 가장 마지막에 들어온 것이 가장 크다
따라서 작은 것을 만났을 때 가장 먼저 나가야 한다.
- Stack 이용
stack에는 pair로 가격과 인덱스를 넣자
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for문으로 가격들을 순회한다
1. 스택이 비어 있다면
A. Pair를 만들어주고 스택에 push
2. 스택이 비어 있지 않다면
A. 지금 가격과 스택 top에 있는 가격을 비교
i. 지금 가격이 같거나 크다면
1. 스택에 가격과 인덱스 push
ii. 지금 가격이 더 작다면 (떨어지는 순간)
1. Stack에 있는 모든 것들을 비교해 줘야 한다
A. 지금 가격이 같거나 크다면
i. 스택에 가격과 인덱스 push
ii. Break!
2. Stack의 top이 지금 가격보다 크기 때문에 stack pop 해주고 인덱스로 시간 계산
A. Stack에 남은 것이 없다면(모든 원소가 자신보다 큼)
i. 지금 가격과 인덱스 push
3. 모든 순회가 끝나면
A. Stack에 남아 있는 것 만큼 인덱스 계산
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
typedef pair<int,int> p;
vector<int> solution(vector<int> prices) {
vector<int> answer;
stack<p> s;
answer.resize(prices.size());
for(int i=0;i<prices.size();i++){
if(!s.size()) // 스택이 비었다면
{
p temp = make_pair(prices[i],i);
s.push(temp);
}
else{
int tempPrice = s.top().first;
int nowPrice = prices[i];
if(tempPrice <= nowPrice){
p temp = make_pair(prices[i],i);
s.push(temp);
}
else{
while(s.size()){
tempPrice = s.top().first;
p temp = make_pair(prices[i],i);
if(tempPrice <= nowPrice){
s.push(temp);
break;
}
int tempIndex = s.top().second;
s.pop();
answer[tempIndex] = (i - tempIndex);
if(!s.size()){
s.push(temp);
break;
}
}
}
}
}
while(s.size()){
int tempIndex = s.top().second;
answer[tempIndex] = (prices.size() - 1 - tempIndex);
s.pop();
}
return answer;
}
