[백준/BOJ] 백준 2493번 : 탑

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

2493번: 탑

스택을 이용하여 문제를 해결했다. 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

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

	int n;
	int input;
	stack<pair<int, int>> s;
	vector<int> result;

	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> input;

		//스택에 아무것도 없을때(처음 시작일때)
		if (s.empty())
		{
			result.push_back(0);
			
			//탑의 높이와 번호를 스택에 저장
			s.push(make_pair(input, i));
		}

		//스택 top의 높이가 input 보다 클때
		else if (s.top().first > input)
		{
			result.push_back(s.top().second);
			
			//탑의 높이와 번호를 스택에 저장
			s.push(make_pair(input, i));
		}

		//스택 top의 높이가 input보다 작을때
		else if (s.top().first < input)
		{
			//input보다 높은 탑을 찾을때 까지 스택pop
			while (!s.empty() && s.top().first < input)
			{
				s.pop();
			}

			//input보다 높은 탑이 없었을때
			if (s.empty())
				result.push_back(0);

			//input보다 높은 탑을 찾았을때
			else
				result.push_back(s.top().second);
			
			//탑의 높이와 번호를 스택에 저장
			s.push(make_pair(input, i));
		}
	}

	for (int i = 0; i < result.size(); i++)
		cout << result[i] << " ";

	return 0;
}