백준 2493번 탑

아이디어:

1. 높이와 위치(인덱스)를 기록하는 스택을 두 개 사용

2. 입력된 높이와 스택 top의 비교를 통해 스택의 내림차순 유지

 

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

// Answer Code
int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, tmp;
	stack<pair<int, int>> S;
	cin >> N;
	S.push({ 100000001, 0 });

	for (int i = 1; i <= N; i++) {
		cin >> tmp;
		while (tmp > S.top().first)
			S.pop();
		cout << S.top().second << " ";
		S.push({ tmp, i });
	}

	return 0;
}

 

1. pair<int, int>를 담는 스택 사용

2. 스택에 {100000001, 0}을 담아 스택의 빈 경우 배제

3. 들어온 입력에 대해 스택 top 보다 작거나 같을 때까지 스택에서 모두 제거

4. 위치 출력

5. 스택에 입력 추가 

---

내 풀이:

1. 높이를 기록하는 스택, 위치를 기록하는 스택 사용

2. 입력된 수에 대해 스택이 비어있을 때, 스택 top보다 크거나 같을 때, 스택 top보다 작을 때로 구분

 

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, tmp;
	stack<int> S, pos;
	cin >> N;

	for(int i = 1; i <= N; i++) {
		cin >> tmp;
		
		if (S.empty()) {
			S.push(tmp);
			pos.push(i);
			cout << 0 << " ";
		}
		else if (tmp >= S.top()) {
			while (!S.empty() && tmp >= S.top()) {
				S.pop();
				pos.pop();
			}
			if (S.empty()) cout << 0 << " ";
			else cout << pos.top() << " ";
			S.push(tmp);
			pos.push(i);
		}
		else if (tmp < S.top()) {
			S.push(tmp);
			cout << pos.top() << " ";
			pos.push(i);
		}

	}

	return 0;

}