[G5] 백준 2493번 탑 C++ 스택

리뷰

 

스택을 활용하여 O(N) 시간복잡도로 푸는 문제

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

 

전역 변수

• n : 탑의 개수를 저장할 정수형 변수 n
• lst, ans : 탑의 정보를 저장할 정수형 배열 lst, 각 탑에서 본 결과를 저장할 정수형 배열 ans

 

함수

없음

 

 

문제풀이

1. n을 입력 받고 lst 배열에 n개의 탑 정보를 입력 받아준다.
2. 스택을 s로 초기화 해주고 다시 n개의 for문을 개행해 준다.
3. 스택이 비지 않았고, 스택의 top에 해당하는 인덱스의 탑 높이가 현재 탑보다 낮거나 같으면 pop을 해준다.
4. 위 작업을 마친 후 스택이 비어있다면 현재 인덱스의 ans는 0으로, 아니라면 스택의 top인덱스로 저장한다.
5. 현재 인덱스를 스택에 추가해 준다. 해당 작업을 계속 반복해 준다.
6. 반복문이 종료된 후 1 ~ n번 인덱스의 ans배열에 저장된 값을 공백으로 구분하여 출력해 주면 된다.

 

참고 사항

스택에는 인덱스 정보가 들어있어야 한다.

탑의 높이를 비교할때만 lst를 참고하여 비교해 주면 된다.

 

 

정답 코드

#include<iostream>
#include<stack>

using namespace std;
int n;
int lst[500001], ans[500001];

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

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