백준 17298 오큰수

백준 17498←클릭

변수 설정

arr: 입력 배열
rst: 결과값 저장 배열
s: 스택

아이디어

• 배열의 맨 오른쪽 값부터 시작하여 왼쪽과 비교한다.
• 배열의 값 arr[i]와 s.top()을 비교하여 arr[i]가 더 작으면 rst[i]에 s.top()을 삽입
• 배열의 값 arr[i]와 s.top()을 비교하여 arr[i]가 더 크면 s.pop()
• 스택에 arr[i]보다 큰 값이 없으면 rst[i]에 -1 삽입

아래 그림을 보면 이해가 잘 된다.

코드

github

#include<iostream>
#include<stack>
using namespace std;
int N;
int arr[1000000];
int rst[1000000];
stack<int> s;

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	for (int i = N - 1; i >= 0; i--) {
		while (!s.empty() && s.top() <= arr[i]) { //s에 뭔가 있음 + s맨위보다 arr[i]가 더 큼
			s.pop();
		}
		if (s.empty()) {
			rst[i] = -1;
			s.push(arr[i]);
			continue;
		}
		else { //s.top() > arr[i]
			rst[i] = s.top();
		}
		s.push(arr[i]);
	}
	for (int i = 0; i < N; i++) {
		cout << rst[i] << " ";
	}
	return 0;
}

느낀점

옛날 알고리즘 수업에서 배웠던 주식 스팬 알고리즘과 거의 똑같은 문제이다.

정답~.~