[BAEKJOON] 2493번 탑

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

2493번: 탑

문제조건

1. 각 탑의 높이에서 x축에 평행하게 왼쪽으로 레이저 빔을 발사한다.
2. 제일 먼저 레이저를 맞은 탑에서 레이저 신호를 수신한다.
3. 각각 탑에서 쏜 레이저를 어느 탑에서 수신하는가? 수신하는 탑이 없으면 0을 출력

문제는 정말 간단하다. 왼쪽으로 가다가 자신의 높이보다 높은 탑중에 가장 먼저 만나면 그 탑을 저장하면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 500001
using namespace std;

int n;
long long top[MAX];
vector<int> v;
bool judge;
//입력받은 건 탑의 높이! 출력해야하는건 탑의 인덱스!!
int main(){
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> top[i];

	for (int i = n; i >= 1; i--) {
		judge = true;
		for (int j = i; j >= 1; j--) {
			if (top[i] < top[j]) {
				judge = true;
				v.push_back(j);
				break;
			}
			else judge = false;
		}
		if (judge == false) v.push_back(0);
	}
	reverse(v.begin(), v.end());
	for (auto i : v) cout << i << ' ';
}

역시나 시간초과가 날 줄 알았다. 브루트포스로 완전탐색을 돌리게 되면, n이 50만 까지 인데 n^2 의 시간복잡도를 가지게 되면 엄청나게 복잡도가 늘어난다.

따라서 nlogn 시간 혹은 n시간에 끝낼 방법을 찾아보자.

 

이 문제도 역발상으로 시간을 단축시킬수있다!

만약 레이저를 송신받은 탑이 있다면 송신받은 탑으로 송신한 탑 오른쪽 탑들은 전부 송신하는 탑과 받은 탑사이에는 도달할 수 없다는 것을 알 수 있다. '단 하나의 탑에서만 수신이 가능하다. ' 라는 조건을 보면 알 수있다.

정리 해보면, 높은 탑은 계속해서 남아 있어야하고 낮은 탑은 어차피 만날일이 없기 때문에 지워져도 괜찮다는 말이다.

이 점을 이용해서 시간복잡도를 줄여보자.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#define MAX 500001
using namespace std;

int n;
stack<pair<int, int>> s;
bool judge;
//입력받은 건 탑의 높이! 출력해야하는건 탑의 인덱스!!
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int h;
		cin >> h;
		while (!s.empty()) {
			if (h < s.top().first) {
				cout << s.top().second << ' ';
				break;
			}
			s.pop();
		}
		if (s.empty()) cout << "0 ";
		s.push({ h,i });
	}
}

 

스택이 비었다면, 더 높은 탑이 없기에 만날 탑이 없다는 의미이므로, 0을 출력하도록 했다.