C++ / 백준 / 2493 / 탑

문제

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

2493번: 탑

문제풀이

입력을 받는 vector<int>tower, 답을 저장하기 위한 vector<int>answer, 스택을 쌓기 위해 stack<int>s를 선언한다.

스택 s에는 타워의 번호 값을 저장한다.

for문을 통해 가장 왼쪽에 있는 타워부터 오른쪽으로 이동하면서 비교를 한다.

만약 현재 스택의 top() 부분의 타워의 높이가 현재 비교하려는 타워 높이보다 높거나 같으면 레이저를 수신할 수 있으므로 answer에 s.top()+1 값을 저장한다.

그렇지 않다면, 스택을 pop() 하면서 현재 비교하려는 타워 높이 이상인 타워가 있는지 스택 s가 빌 때까지 while문을 통해 반복하면서 찾는다.

찾게 되면 마찬가지로 answer에 타워의 번호를 저장한다.

존재하지 않아 스택이 비게 되면 while문을 종료한다.

조건문을 돌고 현재 타워의 번호를 스택에 입력한다.

 

코드

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

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N(0), idx(0);
	cin >> N;

	vector<int>tower(N, 0);
	vector<int>answer(N, 0);
	stack<int>s;

	for (idx = 0; idx < N; ++idx)
		cin >> tower[idx];

	s.push({ 0 });
	for (idx = 1; idx < N; ++idx) {
		if (tower[s.top()] >= tower[idx]) {
			answer[idx] = s.top() + 1;
		}
		else {
			while (s.size() > 1) {
				s.pop();
				if (tower[s.top()] >= tower[idx]) {
					answer[idx] = s.top() + 1;
					break;
				}
			}
		}
		s.push(idx);
	}
	for (idx = 0; idx < N; ++idx)
		cout << answer[idx] << ' ';
}