카라멜마끼아또

개인 공부를 위한 공간입니다
상업적 용도로 활용되지 않습니다

https://level.goorm.io/exam/167337/%EB%92%A4%ED%86%B5%EC%88%98%EA%B0%80-%EB%94%B0%EA%B0%80%EC%9B%8C/quiz/1

풀이

스택을 이용하는 문제

문제에 나와있는

** A 산봉우리에서 B산봉우리를 보기 위한 조건?

1. A가 B보다 왼쪽에 있어야 하고 (A < B)

2. A와 B 사이에 있는 모든 산봉우리가 A보다 작아야 한다

라는 조건을 활용

산봉우리를 왼쪽부터 순서대로 선택

스택의 top을 살펴보고, 현재 선택된 산봉우리보다 작으면 pop

>> 왜? 현재 선택된 산봉우리보다 작은 산봉우리는 현재 선택된 산봉우리를 포함하여 오른쪽에 있는 모든 산봉우리도 볼 수 없기 때문에

현재의 값을 push 하면 스택의 크기가 선택된 산봉우리를 볼 수 있는 산봉우리의 개수가 됨

int main() {

	int n;	// 산봉우리 개수
	cin >> n;

	stack<int> s;
	vector<int> answer;		// 정답을 담을 vector

	answer.push_back(0);	// 제일 왼쪽 산봉우리는 바라보는 신선이 없으므로 항상 0

	for (int i = 1; i < n; i++) {
		int input;		// 산봉우리의 높이 입력
		cin >> input;
		
        // 스택이 비어있지 않고, top() 보다 input의 값이 크거나 같다면
		while (!s.empty() && s.top() <= input)
			s.pop();	// 스택의 값을 pop
		
        // 그 후 스택에 현재 input을 push
		s.push(input);
        
        // 스택의 size를 answer vector에 저장
		answer.push_back(s.size());

	}

	// 정답 출력
	for (auto a : answer)
		cout << a << " ";
	
	return 0;

}