[백준] 2493 탑 C++

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

 

 

해설

이전 오큰수 문제와 굉장히 비슷한 문제이다. 

탑이 수신가능한 탑 번호를 매겨야하는데, 자신보다 왼쪽에 있으면서 큰 탑의 번호를 넣어주어야한다.

계산의 편의성을 위해서 입력 받은 벡터를 뒤집고 계산한뒤 나중에 다시 뒤집는다.

그럼 이제 자신보다 크면서 오른쪽에 있는 탑의 번호를 찾으면 되기 때문에 마찬가지로 스택을 사용해서 풀어준다.

 

코드

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <stack>
#include <sstream>
#include <set>
#include <unordered_set>
#include <cmath>

using namespace std;
using ll = long long;
#define endl "\n"

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	vector<int> ret, arr;
	stack<pair<int, int>> stk;
	int n; cin >> n;
	ret.resize(n);
	for (int i = 0; i < n; ++i)
	{
		int a; cin >> a;
		arr.push_back(a);
	}

	reverse(arr.begin(), arr.end()); // 뒤집는다.

	for (int i = 0; i < arr.size(); ++i)
	{
		int now = arr[i];
		if (stk.empty())
		{
			stk.push({ now, i });
		}
		else
		{
			if (stk.top().first > now)
			{
				stk.push({ now, i });
			}
			else
			{
				while (stk.empty() == false && stk.top().first < now)
				{
					ret[stk.top().second] = n - i;
					stk.pop();
				}
				stk.push({ now, i });
			}
		}
	}

	while (!stk.empty())
	{
		ret[stk.top().second] = 0;
		stk.pop();
	}
	
	reverse(ret.begin(), ret.end());
	for (int a : ret) cout << a << " ";

	return 0;
}

 

후기

오큰수와 비슷한 문제이다.

while문을 돌면서 현재 탑 보다 길이가 작은 탑의 수신 탑 번호를 매기는 부분에서 벡터 배열을 한번 뒤집었기 때문에

n - i를 통해 올바른 번호를 매길 수 있도록 한게 포인트라고 생각한다.