백준 2493 탑 C++

https://www.acmicpc.net/problem/2493

2493번: 탑

 

DP로 풀 수 있고 Stack으로도 풀 수 있다. 둘 다 어렵지 않은 풀이지만, Stack 풀이가 뇌용량을 덜 쓴다.

 

우선 Dp로 풀었다.

만약 탑이

6 4 5 7 3

순으로 배치되어있다면 답은 "0 1 1 0 4" 이다.

 

여기서 '5'를 잘 봐야하는데, 5는 일단 바로 앞의 값을 본다. '4'다. 본인보다 높이가 낮으므로 전파가 닿지않는다. 

무식하게 할 경우 여기서 6을 보게 된다. 운 좋게 맞는 말을 하게됐지만  만약 숫자 배열이 6 0 4 5 7 3이라면 0을 보게된다.

이런 방법은 최악의 경우 O(N^2)를 기록할 수밖에 없다.

 

대신 '4'의 전파가 가닿는 곳을 본다. 그러면 6 0 4 5 7 3이더라도 바로 6을 보게된다.

 

코드를 보면 이해가 빠를 것이다.

 

#pragma once
/* 탑 */

#include <iostream>

#define MAX_HEIGHT 500000 + 1

using namespace std;

int N;
int dp[MAX_HEIGHT], height[MAX_HEIGHT];

void input();
void solve();

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	input();
	solve();

	return 0;
}

void input() {
	cin >> N;
	cin >> height[1];
	dp[0] = -1;
	dp[1] = 0;

	for (int i = 2; i <= N; i++) {
		cin >> height[i];

		if (height[i - 1] >= height[i]) {
			dp[i] = i - 1;
		}
		else {
			int idx = i - 1;
			while (dp[idx] != -1 && height[dp[idx]] < height[i]) {
				idx = dp[idx];
			}

			if (dp[idx] != -1) {
				dp[i] = dp[idx];
			}
		}
	}
}

void solve() {
	for (int i = 1; i <= N; i++) {
		cout << dp[i] << " ";
	}
}

 

그 다음은 Stack을 활용한 풀이방법이다. 이 방법이 더 간단한 것 같다. 대신 공간 및 시간 복잡도 자체는 DP를 활용한 방법이 더 낫다.

 

Stack을 활용한 방법은

'제일 가까운 최고점 그 다음 block에 닿을 수 없다.'를 기반으로 한다. 무슨 말이냐면

1 3 5 2 6 8 9 3 4 

이런 블럭이 있을 때 

네 번째에 있는 '2'는 두 번째에 있는 '3'에 전파를 보낼 수가 없다. '5'가 가로막고 있기 때문이다. 그러므로 stack에 최고점만 쌓아 나간다면 결과적으로 stack은 Non-Increasing Order가 된다.  코드를 보면 더 잘 알 수 있다.이해가 잘 안되면 손으로 Test case를 하나하나 해보면 된다.

 

#pragma once
/* 탑 */

#include <iostream>
#include <stack>

#define MAX_HEIGHT 500000 + 1

using namespace std;

int N, height, cnt;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	stack<pair<int,int>> s;

	for (int i = 1; i <= N; i++) {
		cin >> height;

		while (!s.empty()) {
			if (s.top().second > height) {
				cout << s.top().first << " ";
				break;
			}

			s.pop();
		}

		if (s.empty()) cout << 0 << '\n';
		s.push({ i, height });
	}

	return 0;
}