크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.
예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.
4
3 5 2 7
5 7 7 -1
4
9 5 4 8
-1 8 8 -1
스택을 이용한 풀이 문제이다!
input과 output 배열을 만들어 주었고,
수열을 input 배열에 쭉 입력받았다.
input 배열의 뒤에서부터 검사를 실행한다.
현재 요소를 검사하는 알고리즘은 다음과 같다.
스택이 비어있지 않고, 스택의 맨 위 요소가 현재 요소보다 작거나 같으면, 스택의 맨 위 요소를 없앤다. --> 스택이 비거나 스택의 맨 위 요소가 현재 요소보다 클 때까지 반복
1번이 끝난 후, 스택이 비어있으면 현재 요소의 output 값은 -1이다.
1번이 끝난 후, 스택이 비어있지 않으면 현재 요소의 output 값은 스택의 맨 위 요소이다.
2번 혹은 3번이 끝난 후, 스택의 맨 위에 현재 요소를 넣어준다.
1번은 현재 요소보다 큰 요소가 오른쪽에 있었는지 찾는 과정이다.
1번에서 오른쪽에 현재 요소보다 큰 요소가 없다면 스택이 빌 때까지 pop할 것이고, 2번에서 output에 -1을 넣어줄 것이다.
1번에서 오른쪽에 현재 요소보다 큰 요소가 있다면, pop을 하는 while문이 종료될 것이고, 현재 스택의 가장 위에 있는 요소는 현재 요소보다 큰 요소 중 가장 왼쪽에 있는 요소일 것이다. 그러므로 3번에서 현재 요소의 output 값에 스택의 맨 위 요소를 넣어줄 것이다.
"현재 요소보다 큰 요소 중 가장 왼쪽에 있는 요소"를 A라고 할 때
2번 혹은 3번을 진행한 후에,
현재 요소는 ->
여태까지 확인한 요소 중,
A의 왼쪽에 있고,
A보다 작은 값 중에 가장 큰 값이 된다.
그러므로 스택의 가장 윗부분에 push해준다.
스택은 항상 위에서부터 아래로 오름차순으로 정렬되어 있을 것이다.
마지막으로 output array를 쭉 출력해 주면 정답이다.
#include <iostream>
#include <stack>
using namespace std;
void input_data(void);
void right_biggest(void);
void prt_result(void);
int input[1000000];
int output[1000000];
int n;
stack<int> stk;
int main(void)
{
input_data();
right_biggest();
prt_result();
return (0);
}
void input_data(void)
{
cin >> n;
int i = -1;
while(++i < n)
cin >> input[i];
return ;
}
void right_biggest(void)
{
int i = n;
while (--i >= 0)
{
while (!stk.empty() && stk.top() <= input[i])
stk.pop();
if (stk.empty())
output[i] = -1;
else
output[i] = stk.top();
stk.push(input[i]);
}
return ;
}
void prt_result(void)
{
int i = -1;
while(++i < n)
cout << output[i] << " ";
return ;
}
히히😀😀