백준 17298 오큰수 [C++] 코드 및 풀이
문제
크기가 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)을 공백으로 구분해 출력한다.
코드
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
if (n == 1)
{
cout << "-1";
return 0;
}
vector<int> in(n, 0);
for (int i = 0; i < n; i++)
{
cin >> in[i];
}
vector<int> res(n, 0);
stack<int> stac;
stac.push(0);
for (int i = 1; i < n; i++)
{
//A번
while (!stac.empty() && in[stac.top()] < in[i])
{
res[stac.top()] = in[i];
stac.pop();
}
stac.push(i);
}
//B번
while (!stac.empty())
{
res[stac.top()] = -1;
stac.pop();
}
for (int i = 0; i < n; i++)
{
cout << res[i] << " ";
}
return 0;
}풀이
예제 입력 1
예제는 다음과 같습니다.
4
3 5 2 7A번 설명
특정 수를 기준으로, 오른쪽 수 중 큰 수가 있는 경우 가장 왼쪽에 있는(즉 자신과 가장 가까운) 수가 특정 수의 오큰수입니다.
3 5 2 7 4개 수의 오큰수를 확인하면 다음과 같습니다.
7의 오른쪽은 아무것도 없으니 -1로 결과값에 저장이 됩니다.
그럼 반복의 수를 줄이기 위해서라도 생각해야 하는 부분은 다음과 같습니다.
1. 가장 오른쪽에 있는 수를 먼저 비교한다.
2. 자신과 가장 가까운 큰 수를 찾는다.
또한, 그림으로 보았을 때, 오큰수를 찾아야 하는 특정 수의 index가 높아질 수록 이전 index의 요소들은 필요 없다는 것 입니다.
뒤에서부터 한다면, 여러모로 반복 수가 증가합니다.
뒤에서부터 한다 했을 때, 찾기 쉬울 것 같지만 만약 5 1 2 4 5 6가 있다고 보았을 때 가장 왼쪽에 있는 5의 오큰수를 찾는데 있어서 다시 오른쪽 수를 끄집어내야하기 때문에, 반복수가 증가합니다.
따라서 앞에서 부터 찾아가는 것이 좋겠습니다.
이제 오큰수를 찾는 방법을 그림으로 보겠습니다.
다음과 같이 특정 수 즉 오큰수를 찾아야 하는 기준을 stack에 먼저 push합니다.
특정 수(3)이 먼저 stack에 있었고 이와 오른쪽 수를 비교하기 위해서는, i가 1부터 시작해야 할 것입니다.
그림과 같이 3 오른쪽에 있는 5가 더 크니 3의 오큰수는 5가됩니다.
이때 정답 배열에 index[0]번 즉 3번의 정답은 5가 들어가야 하는데 이를 어떻게 할지 생각 해 보겠습니다.
stack.top은 3이 들어가있고 3의 index는 0입니다.
그럼 stack에 index를 넣어주면 정답 배열도 해당 index를 사용할 수 있겠습니다.
따라서 stack에는 입력 배열의 index를 넣어주면 됩니다.
이후 3의 오큰수는 찾아 주었으니 이제 필요가 없어졌습니다.
따라서 stack에서 pop을 해줍시다.
이제 현재 i가 1이고, 입력 배열[1]은 다음 오큰수를 찾아야하는 특정 수 이기 때문에, 이 수를 stack에 넣어 줍시다.
이제 5의 오큰수를 찾아줄 때 입니다.
비교 해 보았을 때, 5의 오큰수 자리에는 2가 들어올 수 없습니다.
따라서 다음 특정 수의 오큰수를 찾으면서 5보다 큰 수 즉 오큰수인지 같이 비교해야합니다.
왜냐하면 5와 가장 가까우면서 큰수가 오큰수로 되어야 하기 때문이죠.
따라서 이를 스택에 잠시 대기 해주고, 5와 비교한 2 즉 입력 배열[2]를 스택에 push해 줍니다.
이제 i가 3이 되면서 보니, 2의 오큰수가 7인 것을 발견했습니다.
이후 2는 stack에서 pop이 되겠죠.
그럼 다시 top은 이전에 오큰수를 못찾은 5가 됩니다.
5도 입력 배열[i]와 비교해주면 5도 찾을 수 있겠죠.
따라서 stack의 top과 입력 배열[i]의 비교 과정은 반복문의 조건으로 두어야 합니다.
그럼 다시 돌아와서 2를 pop한 이후로 보겠습니다.
이렇게 5의 오큰수까지 찾아주게 되었습니다.
이후 7을 stack에 push해주며 끝나게 됩니다.
B번 설명
이제 오큰수를 못찾은 수는 자연스럽게 stack에 남게됩니다.
왜냐하면 반복문의 조건을 보면 알 수 있었습니다.
오큰수를 찾은 stack요소는 pop이 되지만, 오큰수를 찾지 못한 수들은 push만 되기 때문입니다.
따라서 마지막에 stack에 남은 요소들은 -1로 정답배열에 채줘주면 끝입니다.