'스택 응용'에 해당되는 글 1건

BOJ 17298 오큰수

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

문제 설명

어떤 수열이 있는데요. 이 수열의 한 원소를 기준으로 오른쪽에 있는 자신보다 큰 원소 중 가장 왼쪽에 있는 수가 오큰수라고 합니다. 이때 수열에 대해 모든 원소의 오큰수를 구하는 것이 문제입니다. 

이때 오큰수가 없는 경우도 있습니다. 가장 큰 원소이거나 가장 오른쪽에 있는 원소는 오큰수가 없을 수가 있죠. 이때는 -1로 오큰수를 정해줍니다.

예를 들어 3 5 2 7 6 8이라는 수열이 있다면 5 7 7 8 8 -1이 해답이 됩니다. 5의 오른쪽에 있는 큰 수들은 7 6 8이 있는데, 이때 가장 왼쪽에 있는 수가 7이므로 5의 오큰수는 7이 됩니다. 여기까지 이해를 했으면 이제 문제를 풀어보겠습니다.

풀이

이 문제에 대해서 왼쪽부터 시작하지 말고 오른쪽부터 시작하면 접근이 쉽습니다. 가장 오른쪽에 있는 오큰수는 없으니까 -1로 시작하게 됩니다.

가장 최근에 큰 수(A)을 기억하고 있다가 그것보다 작은 수(B)가 나오게 되면 B의 오큰수는 A가 됩니다. 이때 B는 그냥 버리면 안됩니다. 왜냐면 B가 왼쪽 어떤 C의 오큰수 일 수 있으니까요. 그래서 B를 기억하고 있어야합니다. 아래와 같은 상황에서 B는 C의 오큰수가 됩니다. 이때 C도 역시 기억하고 있어야됩니다. C도 어떤 수의 오큰수가 될 수 있게 되니까요. 아래의 그림은 이해하기 쉽게 도형의 크기로 수의 크기를 표현하였습니다.

하지만 C가 B보다 큰 경우 B는 오큰수가 아니게 되겠죠? C 이전의 수들은 B가 필요없게 됩니다. 왜냐면 C가 B보다 크면서 더 왼쪽에 있으니까요. 그래서 B는 이제 기억에서 사라지고 C를 기억하고 있어야됩니다.

자, 이제 뭔가 좀 감이 잡힐 수 있습니다. 가장 최근에 것을 상황에 따라 보관하고 있다가 비교하거나 버리고 하는 것을 알 수 있게 됩니다. 그래서 스택이라는 자료구조가 이 문제에서 사용됩니다.

Stack에는 가장 오른쪽부터 시작해서 오큰수들이 들어가게 됩니다. 이때 value는 현재 수열의 비교할 값을 말한다고 합시다. 스택의 가장 위(top)는 어떠한 오큰수가 들어가게 되는데, value보다 작다면 이 오큰수는 쓸모가 없게 되므로 스택에서 pop하면 됩니다. stack의 top이 value보다 더 클때까지 계속 pop하게 되면 결국 stack이 비게 되거나, value보다 큰 오큰수가 존재하게 됩니다. 

이때 스택이 비어있다면 value의 오큰수가 없다는 것, 비어있지 않다면 스택에 있는 top의 값이 오큰수가 되게 됩니다.

위 설명을 따른 예제에 대한 그림 풀이가 아래에 있습니다. 참고하시기 바랍니다.

전체코드

전체 코드는 아래와 같습니다. 주석처리하여 추가설명하였습니다.

#include <cstdio>
#include <stack>

using namespace std;
int n, numbers[1000001], ans[1000001];

int main() {

	stack<int> st = stack<int>();

	scanf("%d", &n);

	for (int i = 0; i < n; i++) 
		scanf("%d", &numbers[i]);
	
	st.push(numbers[n - 1]);	//가장 오른쪽에 있는 수는 stack에 push
	ans[n - 1] = -1;			//가장 오른쪽의 있는 수는 오큰수가 없으므로 -1
	for (int i = n - 2; i >= 0; i--) {	//거꾸로 for문
		int value = numbers[i];			//stack의 top과 비교할 숫자
		while (!st.empty() && value >= st.top()) {	//스택이 비어있지 않고, 스택의 top이 value보다 작거나 같으면
			st.pop();								//그 수는 버린다.
		}
		//이렇게 되면 두가지 상황이 발생하는데,
		//스택이 비어있으면 value 오른쪽에 오큰수가 없다는 것으로 value의 오큰수는 -1
		//숫자가 남아있다면 value보다 큰 수가 있는 것으로 오큰수는 st.top
		ans[i] = st.empty() ? -1 : st.top();
		
		//그리고 value를 stack에 push
		st.push(value);
	}

	for (int i = 0; i < n; i++) printf("%d\n", ans[i]);
	printf("\n");
}

이상으로 포스팅을 마치겠습니다.