[백준] 탑 보기 22866번 (c++) 스택을 활용한 증가 수열 만들기

출처 : https://www.acmicpc.net/problem/22866

 

풀이 방법

접근 방식

1. 완전 탐색:

• 모든 건물을 순회하며 비교하는 방식은 시간 초과가 발생한다.

• 시간 복잡도:  O(n^2) 

2. DP(동적 프로그래밍) 접근 시도:

• 오른쪽에서 자신보다 크면서 가장 가까운 건물을 선택하여 해당 건물이 볼 수 있는 건물을 자신도 볼 수 있게 한다.

• 하지만, 건물 높이가 계속 감소하는 최악의 경우에는 여전히  O(n^2) 이 되어 효율적이지 않다.

효율적인 풀이 방식

 

스택(Stack)을 사용하여 두 번의 순회로 문제를 해결한다.

• 왼쪽 → 오른쪽 순회

• 오른쪽 → 왼쪽 순회

 

두 과정은 동일하므로 왼쪽 → 오른쪽 순회 과정을 살펴보자

 

알고리즘 동작 방식

1. 스택이 비어있지 않고, 현재 건물보다 스택의 값이 높을 때까지 pop

• 이를 통해 현재 건물보다 큰 건물만 스택에 남게 한다.

• 스택에 남은 값은 현재 위치에서 왼쪽 시야로 볼 수 있는 건물이 된다.

2. 현재 건물을 스택에 push

• 이 과정을 반복하여 자신보다 크고 시야에 보이는 건물만 스택에 저장되도록 한다.

3. 가장 가까운 건물 찾기:

• 스택의 top()과 자신의 거리를 비교하여 가장 가까운 건물을 선택한다.

 

시간 복잡도 분석

• 스택을 이용한 순회는 한 번의 반복으로 해결하므로 O(n)이 된다.

 

 

#include <iostream>
#include <stack>
#include <memory.h>

using namespace std;

int N;
int h[100001], near[100001], cnt[100001];
stack<int> left_s, right_s;

int main() {
	cin >> N;	
	for (int i = 1; i <= N; i++) {
		cin >> h[i];
		near[i] = -100001;
	}
	
	for (int i = 1; i <= N; i++) {		
		while (!left_s.empty() && h[left_s.top()] <= h[i]) left_s.pop();
		if (left_s.size() != 0) {
			cnt[i] = left_s.size();
			near[i] = left_s.top();
		}
		left_s.push(i);
	}

	for (int i = N ; i > 0; i--) {
		while (!right_s.empty() && h[right_s.top()] <= h[i]) right_s.pop();
		if (right_s.size() != 0) {
			cnt[i] += right_s.size();
			if (near[i] == 0) near[i] = right_s.top();
			if (i - near[i] > right_s.top() - i) near[i] = right_s.top();
		}
		right_s.push(i);
	}
	for (int i = 1; i <= N; i++) {
		if (cnt[i] == 0) cout << 0 << '\n';
		else { // 갯수와 번호를 적는다.
			cout << cnt[i] << " " << near[i] << '\n';
		}
	}
	return 0;
}