백준 6198번 옥상 정원 꾸미기

문제 링크입니다: https://www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

스택을 이용하는 문제였습니다.

1. 스택의 top에 위치한 빌딩의 높이가 i 번째 빌딩의 높이보다 작거나 같을 경우 i 번째 빌딩의 옥상을 볼 수 없으므로 스택의 top이 i 번째 빌딩의 높이보다 높을 때까지 pop을 해줍니다.

2. 스택에 i 번째 빌딩의 높이를 push 해줍니다.

3. i 번째 빌딩을 제외한 나머지 빌딩들이 i 번째 빌딩의 옥상을 볼 수 있으므로 결과에 (스택의 크기 - 1)을 더해줍니다.

 

* 주의: 결과의 자료형은 long long 형이여야합니다. N이 80,000이고 빌딩의 높이들이 동일하지 않은 상태에서 내림차순으로 주어진다면 정답이 int 형의 범위를 벗어나기 때문입니다.

 

	#include <iostream>
	#include <stack>
	#include <algorithm>
	using namespace std;
	const int MAX = 1e5 * 8;
	int buildings[MAX];
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
	cin >> buildings[i];
	}
	stack<int> s;
	long long result = 0;
	for (int i = 0; i < N; i++)
	{
	while (s.empty() == false && s.top() <= buildings[i])
	{
	s.pop();
	}
	s.push(buildings[i]);
	result += s.size() - 1;
	}
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~