[G4] 백준 17298번 오큰수 C++ 스택

리뷰

 

스택을 활용하여 리스트의 뒤에서부터 순차적으로 순회하며 오큰수를 찾는 문제

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

 

전역 변수

없음

 

 

함수

없음

 

 

문제풀이

1. n을 입력 받고 수와 정답을 저장할 벡터lst, result의 크기를 n으로 초기화 해주고 n개의 수를 입력 받아 저장한다.
2. 스택을 초기화 해준 뒤에 n - 1부터 0번 인덱스 까지 lst를 반대로 순회해 줄것이다.
3. 스택이 비지 않았을 경우 스택의 제일 위 요소와 현재 값을 비교한다.
4. 스택의 제일 위 요소가 현재 값보다 작거나 같으면 스택에서 제거해 준다. 이 작업을 반복해 준다.
5. 위 작접이 완료된 후 만약 스택이 빈 상태라면 result의 현재 인덱스 값을 -1로 저장한다.
6. 만약 스택이 빈 상태가 아니라면 스택의 마지막 요소를 result의 현재 인덱스 값으로 저장한다.
7. 이후 스택에 현재 숫자를 추가해 준다.
8. 위 작업을 마친 뒤 result에 저장되어 있는 값을 공백으로 나누어 출력해 주면 된다.

 

참고 사항

처음엔 현재 위치에서 부터 upper_bound를 사용하려 했으나 수열이 정렬된 상태가 아니라 이상한 값이 나왔다.

된다 하더라도 시간 복잡도가 O(NLogN)이므로 스택을 사용한 O(N) 보다 컸다.

그런데도 생각보다 시간이 오래 걸린 것 같다.

 

정답 코드

#include<iostream>
#include<vector>
#include<stack>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n; cin >> n;
	vector<int> lst(n), result(n);
	for (int i = 0; i < n; i++) cin >> lst[i];
	stack<int> s;
	for (int i = n - 1; i >= 0; i--) {
		while (!s.empty() && s.top() <= lst[i]) s.pop();
		if (s.empty()) result[i] = -1;
		else result[i] = s.top();
		s.push(lst[i]);
	};
	for (int i = 0; i < n; i++) cout << result[i] << " ";
}