[알고리즘] 탑

구현 방식

• 스택이 비어있으면 왼쪽 값이 없으므로 0 출력,
• 스택이 비어있지 않으면 top 부분이 현재 입력으로 들어온 높이보다 크면 해당 top 부분의 인덱스값출력
• 작다면 스택에서 pop 후 이후 top 탐색
  • 현재 들어온 높이값보다 작은 값이라면, 어차피 이후에 들어오는 값들은 해당 높이값으로 수신받질 않을 것이므로 pop 해도 된다.

코드

• 최종 코드는 아래와 같다.

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

	int N;
	cin >> N;

	// idx , value
	stack<pair<int,int>> s;

	for (int i = 1; i <= N; i++)
	{
		int h;
		cin >> h;

		while (!s.empty())
		{
			int recvIdx = s.top().first;
			int recvheight = s.top().second;

			if (h <= recvheight)
			{
				cout << recvIdx << " ";
				s.push({ i,h });
				break;
			}
			else
			{
				s.pop();
			}
		}

		if (s.empty())
		{
			cout << 0 << " ";
			s.push({ i,h });
			continue;
		}

	}

}