백준 - 17608번 막대기 (C++)

Pixabay로부터 입수된 PublicDomainPictures님의 이미지 입니다.

 

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

17608번: 막대기

 

 이번 문제는 높이만 다른 막대기를 세운 후, 이것들을 오른쪽에서 본다면 막대기가 몇 개 보일지를 구하는 문제이다. 막대기가 보이기 위해서는 해당 막대기의 오른쪽에 자신보다 큰 막대기가 없어야 할 것이다. 예를 들어, 높이가 3인 막대기의 오른쪽에 높이가 9인 막대기가 있다면, 높이가 3인 막대기는 높이가 9인 막대기에 막혀 보이지 않을 것이다. 그렇기에 오른쪽에서 보이는 막대기의 개수를 구하기 위해서는 오른쪽을 기준으로 점점 높이 값이 커지는 개수를 구하면 된다.

 예를 들어, 첫 번째 예제에서는 6, 7, 9순으로 커지므로 답은 3이 되며 두 번째 예제에서는 1, 2, 3, 4, 5 순으로 커지므로 답은 5가 된다. 그리고 이를 구현하기 위해서 스택을 이용한다. 만약 막대기의 높이가 주어졌을 때, 스택이 빈 상태라면 push를 한다. 그리고 스택에 값이 들어있다면 해당 막대기 높이보다 작거나 같은 값은 전부 pop을 한 후, 해당 높이 값을 push한다. 그리고 stack에 있는 값의 개수가 답이 된다.

 

#include <iostream>
#include <stack>

using namespace std;

int N;
int answer = 0;
stack<int> stk;

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

	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		int height;
		cin >> height;

		if (stk.empty())
			stk.push(height);
		else
		{
			while(!stk.empty())
			{
				if (stk.top() <= height)
					stk.pop();
				else
					break;
			}

			stk.push(height);
		}
	}	

	while(!stk.empty())
	{
		++answer;
		stk.pop();
	}


	cout << answer << endl;
	
    return 0;
}