💡 자료 구조/스택
Memory 9236KB Time 220ms Code Length 707B
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
#include <iostream>
#include <vector>
using namespace std;
int num;
int height[500000];
vector<int> result;
void init() {
scanf("%d", &num);
for (int i = 0; i < num; i++) {
scanf("%d", &height[i]);
}
}
int main() {
init();
vector<int> v; // 인덱스를 저장하는 벡터
for (int nowi = 0; nowi < num; nowi++) {
while (!v.empty() && height[v.back()] <= height[nowi]) {
v.pop_back();
}
if (v.empty()) {
result.push_back(0);
} else {
result.push_back(v.back() + 1);
}
v.push_back(nowi);
}
for (int i = 0; i < num; i++) {
printf("%d ", result[i]);
}
return 0;
}
이 코드는 주어진 높이 배열에서 각 인덱스의 높이보다 크거나 같은 이전 인덱스들의 위치를 저장하는 것이다. 초기화 함수 init()에서 높이 배열을 입력받고, main() 함수에서는 인덱스를 저장하는 벡터 v를 이용하여 각 인덱스의 결과를 계산한다. 현재 인덱스의 높이가 v에 저장된 인덱스의 높이보다 크거나 같을 때까지 v에서 pop_back()을 수행하고, 그 결과를 result 벡터에 저장한다. 최종적으로 result 벡터에 저장된 값을 출력한다.
