백준 17298번: 오큰수

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

17298번: 오큰수

 

 

0. 알고리즘 분류

 자료구조, 스택

 

 

1. 문제

 

 

2. 풀이

 이게 왜 스택 문제인지 몰랐다. 언뜻 봐서는 배열만 써서도 풀릴 것 같았다. 풀리긴 하지만 문제는 시간복잡도가 O(n^2)으로 시간초과된다. 때문에 스택을 써야한다. 하지만 내 머리로는 도대체 어떻게 스택을 쓰면 시간복잡도를 줄일 수 있는지 생각해내지 못했다..

 

 구글링의 힘으로 풀었다. 코드가 짧아서 놀랐고, 이게 왜 풀리는지 이해를 못해서 놀랐다. 이해하면 쉽다. 스택에 인덱스를 쌓고, 다음 인덱스의 수열값이 스택의 front()보다 크면, 스택의 인덱스의 새 배열에 값을 저장시켜 준다. 이해하기 어렵겠지만 코드를 읽어보면 이해하기 쉬울 것이다.

 

 스택을 이런 식으로 쓸 수 있다는 것이 정말 새롭다...

 

 

3. 코드

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	int n;
	cin >> n;
	
	int a[n];
	stack<int> s;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	
	int b[n];
	fill_n(b, n, -1);
	for (int i = 0; i < n; i++) {
		while (!s.empty() && a[s.top()] < a[i]) {
			b[s.top()] = a[i];
			s.pop();
		}
		
		s.push(i);
	}
	
	for (int i = 0; i < n; i++) {
		cout << b[i] << ' ';
	}
	
	return 0;
}