스택을 사용하는 문제이다.
입력받은 배열을 거꾸로 돌면서 스택의 탑에 위치한 값이 현재 배열 값보다 작다면 팝한다.
만약 스택이 비어있다면 -> 현재값보다 큰 값이 오른쪽에 위치하지 않았다는 의미이므로 -1을 푸쉬한다.
먄약 스택이 비어있지 않다면 -> 스택의 탑값을 결과값에 푸쉬한다. 탑에 있는게 가장 왼쪽에 있는 값이기 때문이다.
그리고 항상 마지막엔 현재 값을 푸쉬해준다.
//오큰수 오른쪽에 있으면서 a보다 큰 수 중 가장 왼쪽에 있는 수
#include <stdio.h>
#include <stack>
using namespace std;
int arr[1000001];
stack<int> st;
stack<int> res;
int main(void)
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
for (int i = n - 1; i > -1; i--)
{
int cur = arr[i];
while (!st.empty() && st.top() <= cur)
{
st.pop();
}
if (st.empty())
{
res.push(-1);
}
else
{
res.push(st.top());
}
st.push(cur);
}
while (!res.empty())
{
printf("%d ", res.top());
res.pop();
}
return 0;
}
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
[백준 1520] 내리막 길 (0) | 2021.01.23 |
---|---|
[백준 1655] 가운데를 말해요 (0) | 2021.01.14 |
[백준 13305] 주유소 (0) | 2021.01.14 |
[백준 9184] 신나는 함수 실행 (0) | 2021.01.13 |
[백준 20055] 컨베이어 벨트 위의 로봇 (0) | 2021.01.13 |
댓글