c++ 6198번 옥상 정원 꾸미기 (백준)

#include <cstdio>
#define M 80001

class Stack { //Stack 구현
private:
	int top;
	int arr[M];
public:
	Stack() : top(0) {} //생성자 top = 0 초기화
	bool isEmpty() {return top == 0;} //비었는가?
	void push(int e) {arr[top++] = e;} //넣기
	int pop() { return arr[--top];} //빼기
	int peek() {return arr[top-1];} //가장 바깥에 있는거
	int cnt() {return top;} //스택에 몇개의 요소가 있는가?
};

int main(void) {
	int n;
	long long int ans = 0; //답은 long long int범위까지 올 수 있습니다.
	Stack s;
	scanf("%d", &n); //입력값의 최대는 10억이므로 int로 처리할 수 있습니다.
	
	while(n--) {
		static int tmp = 0; //요소를 입력받음
		scanf("%d", &tmp);
		if(s.isEmpty()) s.push(tmp); //비어있으면 스택에
		else { //그렇지 않으면
			if(s.peek() > tmp) s.push(tmp); //스택에 있는 것 보다 작다면 스택에 넣어준다.
			else { //그렇지 않으면
				while(s.peek() <= tmp && !s.isEmpty()) { //스택이 비지 않고, 스택의 가장 바깥것 보다 이번에 입력받은 것이 더 크면 스택의 요소를 한 개 뺀다.
					s.pop();
				}
				s.push(tmp); //자신보다 작거나 같은 것을 스택에서 뺀 다음 (자신보다 큰 것이 나오기 전까지) 스택에 집어 넣는다.
			}
		}
		ans += s.cnt()-1; //스택의 개수 - 1을 ans에 누적한다.
	} printf("%lld", ans);
	return 0;
}

풀이 : 스택

건물의 옥상을 보기위해선 오른쪽에 있는 건물이 자신의 건물보다 낮아야 한다.

 

만약 건물이 5층 4층 3층 2층 1층 으로 되어있다면

5층에선 4개의 옥상을

4층에선 3개의 옥상을

3층에선 2개의 옥상을

2층에선 1개의 옥상을

 

볼 수 있으므로 총합은 10개이다.

 

그러나 하나의 건물을 선택한 후 볼 수 있는 옥상의 개수를 구하고,

그 다음 옆에 있는 건물을 선택한 후 볼 수 있는 옥상의 개수를 구하고, 이렇게 일일이 하기엔 시간이 매우 걸리기 때문에

O(n) 속도로 처리하려고 한다.

 

만약 위의 예를 스택에다가 넣어보면 O(n)의 속도로 계산 할 수 있다.

 

1. 5층을 스택에 넣는다

스택 : 5              스택의 길이 1

 

2. 4층을 스택에  넣는다

스택 : 5 4         스택의 길이 2

 

3. 3층을 스택에 넣는다

스택 : 5 4 3        스택의 길이 3

 

4. 2층을 스택에 넣는다

스택 :  5 4 3 2     스택의 길이 4

 

5. 1층을 스택에 넣는다

스택 : 5 4 3 2 1    스택의 길이 5

 

위의 스택을 보면 옥상의 개수를 구할 수 있다.

스택에 요소를 한 개 씩 넣고, 스택의 길이를 구한 다음 이를 누적하면 15가 나오며

여기서 요소의 개수를 빼면 10이 나온다.

 

아까 처음에 일일이 구했던 옥상의 개수와 같은 값이 나온다.

 

즉 요소를 한 개씩 넣고 스택의 길이를 구해서 누적한 다음, 요소의 전체개수로 빼주면

옥상의 개수를 구할 수 있게 된다.

 

옥상의 개수 = 요소를 넣을 때마다의 (스택의 길이 - 1)

 

이해가 되지 않는다면 스택으로 옥상의 길이를 구하는 것은

아래와 같다고 볼 수 있다.

 

5층  : 옥상의 개수 : 0개

5층 4층 : 옥상의 개수 : 1개    5층에서 4층을 봄

5층 4층 3층 : 옥상의 개수 : 2개   5층, 4층에서 3층을 봄

5층 4층 3층 2층 : 옥상의 개수 3개  5층, 4층, 3층에서 2층을 봄

5층 4층 3층 2층 1층 : 옥상의 개수 4개 5층, 4층, 3층, 2층에서 1층을 봄

 

옥상의 개수의 합은 10이며

각각의 옥상의 개수는 그때의 스택의 길이 - 1로 볼 수 있다.

고로

옥상의 개수 = 요소를 넣을 때 마다 (스택의 길이 -1) 이다.

 

 

 

이번에는 문제의 예로 개수를 구해보자

10
3
7
4
12
2

10층 3층 7층 4층 12층 2층 순서대로 스택에 넣어보면

 

stack : 10층

stack : 10층 3층

 

7층을 넣을 땐

 

stack : 10층 7층       이 된다.

 

왜냐하면 3층에선 7층의 옥상을 볼 수 없기 때문이다.

그러므로 3층을 스택에서 pop 한다음

10층과 7층을 비교한다.

10층 > 7층이므로

stack에 7층을 집어넣는다.

 

stack : 10층 7층 4층

stack : 12층  (모든 기존에 있던 스택의 요소보다 더 크기 때문이다)

stack : 12층 2층

 

 

다시 stack의 순서를 가져오면

stack : 10층

stack : 10층 3층

stack : 10층 7층

stack : 10층 7층 4층

stack : 12층

stack : 12층 2층

 

옥상 개수는 각각의 스택에서의 길이 -1 의 합이므로

 

0 + 1 + 1 + 2 + 0 + 1 = 5이다.