탑
맨 오른쪽부터 시작해서 왼쪽으로, 가장 높은 것만 저장하면 된다.
왜?
-
자신 보다 오른쪽에 있는데 가장 높은 것이 자신이 아니라면, 자신이 더 낮다는 뜻.
-
현재까지 가장 높은 높이의 인덱스를 저장할 변수가 있어야 한다.
맨 오른쪽부터 시작
인덱스 기준으로
자신보다 왼쪽에 있는 것이 더 크다면 곧 바로 멈추고 인덱스 변수에 저장 더 작다면 아무일 x
만약 맨 왼쪽까지 갔을 때 자신보다 큰 것이 없다면 자신을 받아줄 신호가 없다.
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
#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<int> solution(vector<int> heights) {
vector<int> answer;
int len = heights.size();
int index = len;
answer.resize(len);
for(int i=len-1;i>=0;i--){
if(index-1 >= i){
for(int j=i-1;j>=0;j--){
if(heights[i]<heights[j]){
index = j+1;
answer[i] = index;
break;
}
if(j==0){
answer[i] = 0;
}
}
}
else{
answer[i] = index;
}
}
return answer;
}
