백준 탑(2493) C++ 풀이

알고리즘 분류

자료 구조

스택

문제 해결 아이디어

스택을 이용하여 전에 있던 탑 중 어떤 크기의 탑(입력한 값보다 크면 됨)이랑 충돌되는지 출력하면 된다.

코드

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

struct Top
{
	int height;
	int location;
};

stack<Top> st;
int n;

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

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

		while (!st.empty())
		{
			if (st.top().height >= num)
			{
				cout << st.top().location << ' ';
				break;
			}
			else
				st.pop();
		}
		if (st.empty()) cout << "0 ";
		st.push({ num, i });
	}
}

코드설명

struct(구조체)를 이용하여 높이와 위치를 함께 정의 할 수 있도록 하고 입력이 들어온데로 현재
스택의 Top()과 높이를 비교하여 Top()의 높이가 더 크거나 같으며 충돌 한 것이기 때문에 Top()의

위치를 출력하면 된다. 만약 더 작으면 계속하여 탐색 할 수 있게 pop()한다.