[백준 문제풀이] 백준 2493 c++ 탑

문제 요약

1. n개의 탑이 생성

2. 각 탑은 왼쪽으로 신호를 보냄

3. 신호를 받으려면 신호를 보낸 탑보다 커야함

4. 신호를 보낸 탑의 노드에서 신호를 받은 탑의 인덱스 출력

5. 신호를 받지 못하는 노드는 0 출력

 

 

스택을 활용해서 깔끔하게 풀 수 있다.

 

입력받은 순서대로 스택에 넣어줘서 input의 마지막 탑부터 처리한다.( 신호는 왼쪽으로 가기 때문에 )

i 노드에서 왼쪽으로 신호를 보내는 것을 확인하기 위해 i-1 번째의 탑과 크기를 비교한다.

 

만약 i-1 번째 탑이 더 크다면 정답 배열에 i-1 노드의 인덱스를 기록하면 된다.

 

i-1 번째 탑이 더 작다면 i 번째 탑을 또 다른 스택에 저장한다.

 

이떄 저장되는 값은 두 번째 스택에서 가장 작은 값일 수 밖에 없다.

 

마찬가지의 논리로 i-1 번째 탑이 더 커서 정답배열에 i-1 노드의 인덱스를 기록한 후, 

 

탑이 커서 신호를 전달하지 못한 탑들의 정보가 담겨있는 두번 째 탑의 크기를  i-1 번째와 비교한다.

 

탑의 크기가 i-1번째가 작을 때 까지 비교하면 된다.

 

#include <iostream>
#include <stack>

int top[500001] = {};

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);

	int n;
	std::cin >> n;

	std::stack<std::pair<int,int>> s;
	int tmp;
	for (int i{ 1 }; i <= n; i++) {
		std::cin >> tmp;
		s.push({ i, tmp });
	}

	std::stack<std::pair<int,int>> s2;
	
	int k = n-1;
	while (!s.empty() && k > 0) {
		int h = s.top().second;
		int num = s.top().first;
		s.pop();

		if (!s.empty() && s.top().second >= h) {
			top[num] = k;
			while (!s2.empty() && s2.top().second <= s.top().second) {
				top[s2.top().first] = k;
				s2.pop();
			}
		}
		else {
			s2.push({ num, h });
		}

		k -= 1;
	}

	for (int i{ 1 }; i <= n; i++) {
		std::cout << top[i] << "\n";
	}
}