BOJ 17298. 오큰수

🙇‍♀️[Gold IV] 오큰수 - 17298

문제 링크

성능 요약

메모리: 12504 KB, 시간: 212 ms

분류

자료 구조, 스택

제출 일자

2024년 1월 17일 12:26:56

문제 설명

크기가 N인 수열 A = A₁, A₂, ..., A_N이 있다. 수열의 각 원소 A_i에 대해서 오큰수 NGE(i)를 구하려고 한다. A_i의 오큰수는 오른쪽에 있으면서 A_i보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -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의 원소 A₁, A₂, ..., A_N (1 ≤ A_i ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

🚀풀이

스택 자료구조를 응용한 문제.

코드는 다음과 같다.

int n;
vector<int> seq;
vector<int> NGE;
stack<int> s;
void setting()
{
    // 수열 채워주기
	cin >> n;
	seq = vector<int>(n + 1);
	NGE = vector<int>(n + 1);
	for (int i = 1; i <= n; ++i)
	{
		cin >> seq[i];
	}
}

// 문제 해결 로직
void solve()
{
	for (int i = n; i >= 1; --i)
	{
		while (s.empty() == false && s.top() <= seq[i])
			s.pop();

		if (s.empty())
			NGE[i] = -1;
		else
			NGE[i] = s.top();

		s.push(seq[i]);
	}

	for (int i = 1; i <= n; ++i)
	{
		cout << NGE[i] << " ";
	}
}

입력 값이 아래와 같을 때 스택의 변화를 알아보자.

4
9 5 4 8

스택과 NGE의 변화 추적.

seq[i] == 8 인 경우

현재 스택 상황
stack
NULL

스택이 비었으므로 NGE[i]에 -1 삽입.
NGE
0 0 0 -1

8을 stack에 push
stack
8

seq[i] == 4 인 경우

현재 스택 상황
stack
8

stack에서 pop되는 값이 없고 NULL이 아니므로 NGE[i]에 8 삽입.
NGE
0 0 8 -1

4를 stack에 push
stack
4 8

seq[i] == 5 인 경우

현재 스택 상황
stack
4 8

4가 5보다 작으므로 pop
stack
8

stack이 NULL이 아니므로 NGE[i]에 8 삽입.
NGE
0 8 8 -1

5를 stack에 push
stack
5 8

seq[i] == 9 인 경우

현재 스택 상황
stack
5 8

5가 9보다 작으므로 pop.
stack
8

8이 9보다 작으므로 pop.
stack
NULL

스택이 비었으므로 NGE[i]에 -1 삽입.
NGE
-1 8 8 -1

9를 stack에 push
stack
9

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

int n;
vector<int> seq;
vector<int> NGE;
stack<int> s;
void setting()
{
	cin >> n;
	seq = vector<int>(n + 1);
	NGE = vector<int>(n + 1);
	for (int i = 1; i <= n; ++i)
	{
		cin >> seq[i];
	}
}

void solve()
{
	for (int i = n; i >= 1; --i)
	{
		while (s.empty() == false && s.top() <= seq[i])
		{
			s.pop();
		}

		if (s.empty())
			NGE[i] = -1;
		else
			NGE[i] = s.top();

		s.push(seq[i]);
	}

	for (int i = 1; i <= n; ++i)
	{
		cout << NGE[i] << " ";
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	setting();
	solve();

	return 0;
}