백준2493 - 탑

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

2493번: 탑

스택을 활용하여 푼 문제다. 스택을 사용하면 확실히 O(n)시간으로 알고리즘을 만들 수 있어서 편리하다. 나는 우선 입력받은 숫자를 리버스하여 생각하였다. 그 다음 스택에 숫자를 넣기 전에 현재 넣을 수보다 작은 수가 있는지 찾는다. 있다면 현재 넣을 숫자의 인덱스를 답으로 넣어준다. 그 다음 스택에 현재 넣을 수를 넣는다. 결과로 나온 답은 리버스한 결과에서 추출한 것이니까 다시 리버스하여 출력한다.

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

int main() {
	std::ios::sync_with_stdio(false);

	int n; //원소의 갯수
	int num; //각각의 숫자 원소
	int cnt = 0; //현재 답으로 넣을 공간을 가리키는 인덱스
	vector<int> v; //입력받은 순서대로 저장할 공간
	vector<int> ans; //답을 저장할 공간
	stack<int> stk; //수를 담아둘 스택

	//안테나의 정보를 입력하고 답으로 설정한 벡터의 모든 원소를 0으로 세팅
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num;
		v.push_back(num);
		ans.push_back(0);
	}

	//역순으로 일단 생각한다.
	reverse(v.begin(), v.end()); 

	//답을 구하는 과정, 나보다 큰 수를 만났을 때 처리
	for (int i = 0; i < n; i++) {
		cnt = i - 1; //답으로 넣을 공간을 우선적으로 현재 숫자 위치에서 바로 직전 위치로 설정한다.
		while (true) {
			if (stk.size() == 0) { //스택이 비어있는 경우
				break; //탈출
			}
			else if (stk.top() < v[i]) { //스택에 꼭대기에 있는 수보다 큰 수를 만난경우
				while (true) {
					if (ans[cnt] != 0) { //숫자를 넣어야 하는데 벌써 들어있는 수가 있으면
						cnt--; //설정한 위치에서 바로 뒤에 공간으로 이동
					}
					else { //숫자를 넣어야 하는 위치가 0이라면
						break; //탈출
					}
				}
				stk.pop(); //꼭대기 수를 뽑고
				ans[cnt] = v.size() - i; //리버스한 것을 기억하여 총 숫자의 갯수에서 현재 위치에 인덱스를 뺀다.
				cnt--; //다음에 넣을 수도 있으니까 현재에서 바로 뒤로 이동
			}
			else { //스택에 꼭대기에 있는 수가 현재 수보다 크면
				break; //탈출
			}
		}
		stk.push(v[i]); //스택에 현재 위치에 숫자를 넣는다.
	}

	//리버스한 숫자들의 모임에서 원소를 찾았으므로 답을 리버스해야 원하는 출력이 나온다.
	reverse(ans.begin(), ans.end()); 

	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << ' ';
	}
}