[C++]백준2493번 탑

오늘은 백준2638번 탑 문제를 풀어보도록 하자.

스택을 이용하는 문제로 만일 이중포문으로 값을 찾으려한다면 데이터의 갯수가 50만개 까지 들어올 수 있으므로 시간초과가 난다.

따라서 스택에 하나씩 넣어서 비교해주며 O(N)의 시간복잡도 로 찾아야한다.

문제는 다음과 같다.

                               [접근법]

  1. 스택의 구조는 {높이, 인덱스}의 형태로 만들어준다.

  2. 만일 스택이 비어있다면 push를 해주고 비교 값이 스택의 맨 위의 값보다 작다면 스택의 맨 위의 인덱스를 출력 후 push
  
  3. 만일 비교 값이 스택의 맨 위의 값보다 크다면 pop을 하고 비어있다면 이 값이 들어올 동안 비교 값보다 큰 값이 없었다는 얘기이므로 0을 출력해준다.

                                     [코드]
#include <iostream>
#include <stack>
using namespace std;
struct info {
	int height;
	int idx;
};
stack<info>s;
int N, num;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num;

		while (!s.empty()) {
			if (s.top().height <= num) {
				s.pop();
				if (s.empty()) {
					cout << 0 << ' ';
				}
			}
			else {
				cout << s.top().idx << ' ';
				s.push({ num, i + 1 });
				break;
			}
		}
		if (s.empty()) {
			s.push({ num, i + 1 });
			if (i == 0) {
				cout << 0 << ' ';
			}
		}
	}
}