백준] 1668 - 트로피 진열

시간 제한 : 2초

메모리 제한 : 128MB

입력

첫째 줄에 트로피의 개수 N (1 ≤ N ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 왼쪽의 트로피부터 차례대로 높이가 주어진다.

출력

첫째 줄에 왼쪽에서 봤을 때 보이는 개수, 둘째 줄에 오른쪽에서 봤을 때 보이는 개수를 출력한다.

소스코드

#include <iostream>
#include <stack>
using namespace std;
int main(void)
{
	int n, arr[50];
	stack<int> sl, sr;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	sl.push(arr[0]);
	for (int i = 1; i < n; i++)
		if (arr[i] > sl.top())
			sl.push(arr[i]);
	sr.push(arr[n - 1]);
	for (int i = n - 2; i >= 0; i--)
		if (arr[i] > sr.top())
			sr.push(arr[i]);

	cout << sl.size() << ' ' << sr.size();
}

Tip

스택을 이용해서 풀었다. 스택의 탑과 비교했을 때 큰 경우에 푸쉬작업을 하고 모든 트로피에 대해 이 작업을 반복해주면, 스택의 사이즈가 답이 된다.