[백준(BOJ) 2493번] 탑 (C++)

문제 링크

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

 

문제 정보

입력

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

출력

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

 

풀이

 이 문제도 어려운 문제여서 해결하는데 힘들었다. 현재 입력하는 탑의 높이가 기존 스택의 탑의 높이보다 크거나 작을때를 잘 생각해주면 된다. 만약 스택의 top이 현재 입력하는 탑의 높이보다 크다면 현재 입력하는 탑의 신호를 받을 수 있다. 그리고 스택의 top이 현재 입력하는 탑의 높이보다 작다면 필요가 없는 탑이므로 pop을 한다.

6 입력 => 스택 : (1, 6)

9 입력 => pop => 스택 : (2, 9)

5 입력 => 스택 : (2, 9), (3, 5)

7 입력 => pop => 스택 : (2, 9), (4, 7)

4 입력 => 스택 : (2, 9), (4, 7), (5, 4)

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	
	stack<pair<int, int>> S;
	
	for (int i = 1; i <= n; i++) {
		int tower;
		cin >> tower;
		
		while (!S.empty()) {
			// top이 현재 입력하는 값보다 크다면 신호를 받을 수 있음!
			if (S.top().second > tower) {
				cout << S.top().first << ' ';
				break;
			}
			// top이 현재 입력하는 값보다 작으면 pop 한다.
			S.pop();
		}
		
		if (S.empty()) {
			cout << '0' << ' ';
		}
		
		S.push(make_pair(i, tower));
	}
	
	return 0;
}