[BOJ] 2493: 탑

1. problem :

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std; 

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

	int N;
	cin >> N;
	stack<int> s;
	vector<int> v(N);
	vector<int> ans(N);
	int i = 0;
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	for (int i = 0; i < N; i++) {
		while (!(s.empty()) && v[s.top()] < v[i]) {
			s.pop();
		}
		if (s.empty()) {
			ans[i] = 0;
		}
		else ans[i] = s.top() + 1;
		s.push(i);
	}
	for (auto c : ans) cout << c << ' ';
	return 0;
}

 

3. solution 2 :

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int N;
stack<pair<int,int>> tower;

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

  cin >> N;  
  tower.push({100000001, 0});
  for (int i = 1; i <= N; i++) {
    int height;
    cin >> height;
    while (tower.top().X < height)
      tower.pop();    
    cout << tower.top().Y << " ";
    tower.push({height, i});      
  }
}

<source code 출처: https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x05/solutions/2493.cpp > 

이 풀이는 stack 제일 밑에 지울 수 없는 height를 하나 설정해 놓아서, empty를 피한다. 그리고 , stack의 element를 제거하면서, stack의 지울 수 없는 element만 있다면, 0을 출력한다. 그 이유는  tower.push({100000001, 0}); 를 해줬기 때문이다. 

만약에 , 이 값이 아닌 다른 값이 있다면, 그 값의 i값을 cout 한다. 

 

여기서 #define X first , # define Y second는 stack의 height와 index에 접근하기 위해서 사용하는 것 같다.