https://www.acmicpc.net/problem/17298
문제
> 크기가 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이다.접근
문제를 요약해보면 오큰수는 수열의 각각의 수에 대해서 오른쪽에 있는 수 중에서 가장 먼저 나오는 본인보다 큰 수이다.
그래서 일단 스택에 나 자신을 넣고 수열을 돌며 나보다 큰 수가 나오면 그 수를 오큰수로 가져 결과 벡터에 저장하고 스택에서 제거한다.
나보다 작은 수는 스택에 넣어준다.
예를 들어 수열이 7,6,5,4,3,8 이렇게 있다면
7을 스택에 넣고 다음 수열의 수들과 비교하는데 6,5,4,3은 전부 7보다 작기 때문에 스택에 들어간다. 이때 8은 7보다 처음으로나온 큰 수 이므로 7의 오큰수가 되는데 6,5,4,3도 어차피 7보다 작은애들이었기 때문에 전부 오큰수가 8이 된다.
이렇게 오큰수를 얻을 수 있기에 스택을 사용할 수 있다.
근데 이제 중간중간 만약 7,5,4,6,3,8 이렇게 있다고 치면
5,4,는 6을 오큰수로 가져 스택에서 빠지지만 7은 여전히 8이 안나와서 스택에 남아있고 스택엔 다시 6,3,이 들어온다.
이때의 오큰수를 단순히 결과 벡터에 저장하게 되면 원래 수열의 순서에 어긎나는 오큰수의 수열을 가지게 된다.
따라서 스택에 수를 넣을때, 그 수와 수의 인덱스까지 같이 쌍으로 넣어 결과 벡터에 저장할 때, rst.push(스택.top().second)로 순서가 섞이지 않게 넣어준다.
문제해결
> num벡터에 수열을 입력받는다.
> 오큰수를 반별하기 위해 스택을 만드는데 스택의 원소를 수열의 수와 그 수의 인덱스를 쌍으로해서 받는다.
> 수열의 각 수에대한 오큰수를 저장할 결과 벡터 rst를 생성하는데 오큰수가 없는 수에 대해 처리해주기 위해 초기값을 -1로 준다.
> for문으로 수열을 돌며 오큰수를 탐색한다.
스택이 비어있으면 비교대상이 없기 때문에 비어있다면 그냥 현재 수열의 수와 인덱스를 넣어주고,
비어있지 않다면 스택의 최상위 값과 수열의 수(num(i))를 비교해 num이 더 크다면 이를 오큰수로 가지고 작다면 스택에 넣어 다시 탐색을 반복해준다.
> 위의 결과로 저장된 rst벡터를 출력해준다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
vector<int> num(N);
for (int i = 0; i < N; i++) cin >> num[i];
stack<pair<int, int>> s;
vector<int> rst(N, -1);
for (int i = 0; i < N; i++)
{
while (!s.empty() && s.top().first < num[i])
{
rst[s.top().second] = num[i];
s.pop();
}
s.push({num[i], i});
}
for (auto& a : rst) cout << a << " ";
}
후기
이게 왜 스택문제인지 고민을 좀 했다.
문제를 다시 읽어보니 자신보다 오른쪽에 있으면서 가장 큰 수를 오큰수로 가지는것이 아닌 오른쪽에 있는 수 중 가장 왼쪽, 즉 가장 먼저 등장하는 나보다 큰 수가 오큰수 였다.
그래서 이걸 단순 반복으로 나보다 큰 애들이 나오면 저장, 다음 수로 넘어가서 또 나보다 큰애 나오면 저장, 이건 시간초과가 날것 같기 때문에 나보다 큰 수를 찾는 과정에서 중간중간 지나치는 수들은 반드시 나보다 작은 애들이기 때문에 스택의 후입선출을 이용해 중간중간 처리해주도록 했다.
그리고 처음엔 그냥했다가 결과가 꼬여서 나와 다시 처음부터 따라가보니 스택의 후입선출 때문에 내가 중간중간 작은애들을 먼저 쳐내기 때문에 결과에 단순히 오큰수를 넣으면 수가 섞였다.
그래서 스택에 인덱스 까지 같이 넣어 오큰수의 저장위치를 지정해주도록 했다.
