백준 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이다.

https://www.acmicpc.net/problem/17298

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 배열이 주어지면 모든 요소들이 자신의 오른쪽에 있는 요소 중 자신보다 크며 가장 가까운 요소를 골라야 한다.

 

일단, 가장 간단한 풀이는 $O(N^2)$으로 배열을 모두 살펴보면 된다.

하지만 시간 초과가 발생할 것이다.

 

따라서, $O(N^2)$시간 보다 적게 풀어야 정답을 구할 수 있다.

 

문제의 조건이 해당 문제를 풀 수 있는 힌트가 된다.

• 자신보다 오른쪽에 있는 수
• 자신보다 크며 가장 가까운 수

우선 자신보다 오른쪽에 있는 수라는 조건은 왼쪽은 살펴볼 필요가 없다는 뜻이 된다.

즉, 배열의 끝에서부터 살펴보는 게 유리하다는 것을 알 수 있다.

 

두 번째 조건이 문제를 풀 수 있는 핵심이다.

만약, 자신의 오른쪽에 있는 모든 수를 저장해 왔다고 가정해 보자.

예를 들어,  A = [3, 5, 2, 7] 일 때, 5에 도착했을 때 [2, 7]을 거쳐왔을 것이다.

5보다 크며 가장 가까운 수를 구하기 위해서는 [2, 7]에서 골라야 한다.

2는 5보다 작으므로 제외시켰을 때, 남은 7이 5보다 크며 가장 가까운 수이다.

 

정리하자면, stack을 이용하여 배열의 끝에서부터 시작하여 모든 수를 저장하고 오큰수를 구하기 위해서는 저장된 stack에서 자신보다 큰 수가 나올 때까지 제외한 후 답을 고르면 된다.

그리고 자신을 stack에 저장한 후 다음 요소도 이를 반복하면 된다. 

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N;
vector<int> nums;
vector<int> answer;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout << fixed;

	cin >> N;
	
	nums.resize(N);
	answer.resize(N);
	for (int i = 0; i < N; i++)
	{
		cin >> nums[i];
	}

	vector<int> stack;

	answer[N-1] = -1;
	stack.push_back(nums[N-1]);
	for (int i = N-2; i >= 0; i--)
	{
		int result = -1;
		while (!stack.empty() && stack.back() <= nums[i])
		{
			stack.pop_back();
		}

		if (!stack.empty()) result = stack.back();
		answer[i] = result;
		
		stack.push_back(nums[i]);
	}

	for (auto ans : answer)
	{
		cout << ans << " ";
	}


	return 0;
}

---