스택활용하기 훈련문제

문제

1. N개의 건물 높이가 주어진다. (최대 80000)

2. 건물옥상에서 좌에서 우측 방향으로만 바라볼 수 있다.

3. 높이가 같거나 높으면 옥상을 볼 수 없다.

4. 이때 옥상을 볼 수있는 최대의 합을 구하라

 

접근

N의 갯수가 최대 8만이기 때문에 i번째 건물'이' 볼 수 있는 옥상을 이중 루프로 비교 탐색을 수행할시 시간복잡도는 O(N제곱)이다. 때문에 시간이 초과될 수 있다.

i번째 건물'을' 볼 수 있는 건물을 탐색해야한다. 시간 복잡도 O(N).

1. i번째 건물을 볼 수 있는 건물을 스택에 저장한다.

2. i+1번째 건물을 볼 수 있으면 pop하지 않는다.

3. i+1번째 건물을 볼 수 없다면 pop한다. 스택에 있는 전체 건물 후보에 대해 2,3을 판단한다.

4. 스택에 남아있는 건물 후보가 i번째 건물을 볼 수 있는 건물이다.

5. 현재 건물을 스택에 push한다.

6. 이를 반복한다.

 

#include <stdio.h>

int N;
long long tower[80000+10];
int stack[80000+10];
int sp = -1;
long long sum=0;

void input()
{
	scanf("%d",&N);
	for(int i=0; i<N; i++)
	{
		scanf("%lld",&tower[i]);	
	}
}

int main() {
	input();
	/*solution*/
	
	for(int i=0; i<N; i++){ //건물 선택 index
		while(sp>=0){
			if(tower[i]>=stack[sp]) sp--; // 현재 건물이 더 높거나 같으면 pop
			else break;
		}
		sum = sum+(sp+1);
		stack[++sp] = tower[i];	//현재 건물 push		
	}
    
    /*
    for(int i=0; i<N; i++){
		for(; (sp>=0) && (H[i] >= stack[sp]); sp-- );
		cnt = cnt + (sp+1);
		stack[++sp] = H[i];
	}
    */
    
	printf("%d\n",sum);
	return 0;
}

 

input

6

4

7

3

4

7

4

 

output

3