백준 2493 탑 [Stack]

문제 링크 : https://www.acmicpc.net/problem/2493

2493번: 탑

문제 풀이

탑을 이중 포문을 돌려서 하나씩 확인하면 시간 초과로 문제를 풀지 못합니다.

stack을 이용해서 O(N)으로 끝내버리는 것입니다.

 

문제의 예시를 보면,

6 9 5 7 4

4번의 탑은 왼쪽으로 송신을 보냈을 때, 수신을 받을 수 있는 탑은 7번입니다.

7번의 탑은 왼쪽으로 송신을 보냈을 때, 수신을 받을 수 있는 탑은 5번이 아닌 9번입니다.

5번의 탑은 왼쪽으로 송신을 보냈을 때, 수신을 받을 수 있는 탑은 9번입니다.

9번의 탑은 왼쪽으로 송신을 보냇을 때, 수신을 받을 수 있는 탑이 없습니다.

6번의 탑도 마찬가지로 수신을 받을 수 있는 탑이 없습니다.

 

스택을 거꾸로 탑을 집어넣으면서 확인해보면 풀 수 있습니다.

핵심은 스택에 top보다 더 큰 탑이 오게 되면 현재 top에 있는 탑을 빼고, 새로운 탑을 push 하는 것입니다.

4번의 탑을 봅니다. 스택이 empty이면 4번의 탑을 스택에 push 합니다.

7번의 탑을 봅니다. 스택의 top에는 4번의 탑이 있지만 7번의 탑이 더 크므로 4번의 탑을 pop하고, 7번의 탑을 push

5번의 탑을 봅니다. 스택의 top보다 작다면 그냥 push 해줍니다.

9번의 탑을 봅니다. 스택의 top보다 크므로 5번의 탑을 pop하고, 7번의 탑 역시 pop 하고, 9번 탑을 push 합니다.

6번의 탑을 봅니다. 스택의 top보다 작다면 그냥 push 해줍니다.

pop 할 때, 그때의 들어온 탑의 번호를 기록해주면 됩니다.

 

소스 코드

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

int main()
{
	//freopen("input.txt", "r", stdin);
	int n;
	cin >> n;
	vector<int> v(n + 1, 0);
	vector<int> ans(n + 1, 0);
	stack<int> st;

	for (int i = 1; i <= n; i++)
		cin >> v[i];

	for (int i = n; i >= 1; i--)
	{
		while (!st.empty() && v[st.top()] < v[i])
		{
			ans[st.top()] = i;
			st.pop();
		}
		st.push(i);
	}

	for (int i = 1; i <= n; i++)
		cout << ans[i] << ' ';

	return 0;
}