[BOJ/C++] 2493 탑

문제

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

풀이

시간 초과에 유의해야 하는 문제✨

O(N)으로 해결해야 한다.
레이저가 젤 가까운 탑에 수신하므로 stack을 이용해서 top()만 보고 수신 탑을 찾으면 된다.

1-1. stack이 비어있는 경우 ➡️수신 탑이 없으므로 0 출력
1-2. stack이 비어있지 않은 경우 ➡️ pop() 해가면서 수신 탑 찾고, 찾은 수신 탑의 index 출력 //stack이 empty 상태가 되면 수신 탑이 없는 것이므로 0 출력
2. (index, 높이)를 pair 형태로 stack에 저장

코드

#include <iostream>
#include <stack>

using namespace std;


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

	int N;
	stack<pair<int, int>> s;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		
		while (!s.empty()) {
			if (tmp <= s.top().second) { //수신탑 찾은 경우
				cout << s.top().first << " ";
				break;
			}

			s.pop();
		}
		if (s.empty())
			cout << 0 << " ";

		s.push({ i + 1, tmp });
	}

	return 0;
}