C++)
#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
int main(void){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int temp = 0;
stack<pair<int, int>> st;
for(int idx = 1; idx <= n; idx++) {
cin >> temp;
// 스택이 비어있지 않고 top에 있는 값이 현재 기준 값보다 작을때까지 뽑아내기
while (!st.empty() && st.top().second < temp)
st.pop();
// 만약 스택이 비어있으면 현재 탑보다 높은 탑이 없다는 뜻이므로 0 출력
// 비어있지 있지 않다면 현재 탑보다 높은 탑이 있다는 뜻이므로 가장 높은 탑의 번호 출력
if (st.empty())
cout << "0 ";
else
cout << st.top().first << " ";
st.push({ idx, temp });
}
return 0;
}
Python)
import sys
read = sys.stdin.readline
n = int(read().rstrip())
top = list(map(int, read().rstrip().split()))
st = []
ans = []
for idx, val in enumerate(top):
# 스택이 비어있지 않고 top에 있는 값이 현재 기준 값보다 작을때까지 뽑아내기
while st and st[-1][1] < val:
st.pop()
# 만약 스택이 비어있으면 현재 탑보다 높은 탑이 없다는 뜻이므로 0 출력
# 비어있지 있지 않다면 현재 탑보다 높은 탑이 있다는 뜻이므로 가장 높은 탑의 번호 출력
ans.append(st[-1][0] if st else 0)
st.append([idx + 1, val])
print(' '.join(map(str, ans)))'백준 1 > 자료구조' 카테고리의 다른 글
| [백준 3015] 오아시스 재결합 (C++/Python) (0) | 2023.06.15 |
|---|---|
| [백준 6198] 옥상 정원 꾸미기 (C++/Python) (0) | 2023.06.14 |
| [백준 1406] 에디터 (Python) (0) | 2021.01.11 |
| [백준 2841] 외계인의 기타 연주 (C++/Java) (0) | 2020.12.06 |
| [백준 3986] 좋은 단어 (C++/Python) (0) | 2020.12.06 |