[BOJ] 2493번 - 탑

<접근 방식>

자기 자신보다 왼쪽에 있으며 가장 가깝고 높이가 높은 탑의 인덱스값을 출력하는 문제이다.

 

스택을 활용하여 오른쪽에서 왼쪽으로 높이를 비교하여 답을 찾는 방식을 사용하였다.

처음에는 2중for문으로 그냥 돌려버렸더니 답은 나왔지만 시간 초과가 걸려버렸다.

해당 2중 for문에 대한 코드만 while문을 사용하여 시간제한을 해결하였다.

 

스택에는 가장 우측부터 탑의 높이와 인덱스를 저장한다.

자기자신보다 높은 탑을 만나면 res배열에 답을 저장하고 처음 res배열은 전역변수로 0으로 초기화 하였기 때문에

자기자신보다 높은 탑을 만나지 못한 경우는 자동적으로 답이 0으로 출력된다.

 

<답은 맞게 나오지만 시간초과 걸린 코드>

#include <iostream>
#include <vector>
using namespace std;

int N, num;
int flag = 1;
int ans;
vector<int> tower;
vector<int> res;
int main()
{
	cin >> N;

	for (int i = 1; i <= N; i++) {
		cin >> num;
		tower.push_back(num);
	}

	for (int i = N - 1; i >= 1; i--) {
		for (int j = i - 1; j >= 0; j--) {
			if (tower[i] < tower[j]) {
				res.push_back(j + 1);
				flag = 1;
				break;
			}
			else {
				flag = 0;
				continue;
			}
		}
		if (flag == 0)
			res.push_back(0);
	}
	res.push_back(0);

	while (!res.empty()) {
		cout << res.back() << " ";
		res.pop_back();
	}
}

<전체 코드>

#include <iostream>
#include <stack>
using namespace std;

int N;
int height[500001];
stack<pair<int,int>> tower;
int res[500001];
int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	
	cin >> N;

	for (int i = 0; i < N; i++) 
		cin >> height[i];
	for (int i = N - 1; i >= 0; i--) {
		while (!tower.empty() && tower.top().first < height[i]) {
			res[tower.top().second] = i+1;
			tower.pop();
		}
		tower.push({ height[i],i });
	}
	for (int i = 0; i < N; i++)
		cout << res[i] << " ";
}

<문제 링크>

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

2493번: 탑