[BOJ] 2493 탑 (C++)

1. 문제 링크

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

 

2. 문제 접근

- 특정 i번째 탑은 레이저 수신을 위해서는 i-j (j < i) 번째 탑에 반드시 자신보다 높은 탑이 존재해야 한다.

- 자신보다 높은 탑을 찾는 과정에서 존재하는 낮은 탑은 관심 없다.

- 즉, 자신이 왼쪽으로 쏘는 시점에서 높이가 높은 탑이 있으면 해당 탑에 레이저를 쏴야하고, 없으면 쏠 대상이 없다.

 

- 6은 아무것도 없기 때문에 레이저를 쏠 대상이 없다.

- 9는 6보다 크기 때문에 6으로 레이저를 쏘는 것이 불가능하다.

※ 이 시점에서, 6을 빼도 되는 이유는 6보다 높이가 더 큰 9가 오른쪽에서 왼쪽으로 쏠 모든 레이저를 받아내기 때문이다.

 

- 5는 9를 향해 레이저를 발사할 수 있다. 하지만 7은 5에게 레이저를 발사할 수 없다.

- 따라서 자신보다 낮은 5를 제거하고, 7을 집어 넣는다. 이후 자신보다 높이가 더 큰 9에게 레이저를 발사한다.

- 마지막으로 들어온 4의 경우, 자신보다 더 높은 7에게 레이저를 발사하게 된다. (9가 있지만 7이 더 가깝다.)

 

3. 문제 풀이

-  stack에 넣기 전에 나보다 stack 값이 작으면 해당 인원은 레이저를 받을 수 없다. 이 경우, pop을 한다.

- stack에 아무것도 남아있지 않다면, 왼쪽으로 레이저를 발사해도 수신하는 탑은 없다.

- 만약 나보다 큰 녀석이 존재하면 해당 인원의 인덱스 값이 해당 번째 수의 정답이 된다.

- 이 문제는 stack에 저장할때, 값뿐만 아니라 해당 탑의 index 정보를 함께 저장해주면 훨씬 유용하다.

 

4. 소스 코드(C++)

#include <iostream>
#include <stack>
using namespace std;
stack <pair<int,int>> value;
int answer[500005] = { 0 };
int tower[500005];
int main(void)
{
	int n;

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	for (int i = 1; i <=n; i++)
	{
		cin >> tower[i];
	}

	for (int i = 1; i <= n; i++)
	{
		while (!value.empty() && tower[i] > value.top().first) // 나보다 값이 작으면 해당 인원은 레이저를 받지 못함.
		{
			value.pop();
		}
		if (value.empty()) // 스택에 아무것도 없다는 것은 레이저를 받아줄 녀석이 없음.
		{
			answer[i] = 0;
		}
		else // 나보다 큰 녀석이 존재함. 해당 녀석의 인덱스가 내 정답임.
		{
			answer[i] = value.top().second;
		}
		value.push({ tower[i],i });
	}

	for (int i = 1; i <= n; i++)
	{
		cout << answer[i] << " ";
	}
}