[백준/BOJ] 백준 26111번 : Parentheses Tree

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

26111번: Parentheses Tree

 

스택에 문자열의 '(' 문자를 넣어가다가, ')' 문자가 나오면, 마지막에 들어온 '('가 해당 ')'의 직전에 들어왔다면 리프노드라는 것을 확인하여 현재 상황의 스택의 크기를 이용하여 해당 리프노드에서 루트노드까지 거리를 구하며 문제를 해결했다.

 

코드

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

long long result = 0;

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

	stack<char> st;
	string input;
	int last_in = -1;

	cin >> input;

	for (int i = 0; i < input.size(); i++) {
		if (input[i] == '(') {
			last_in = i;
			st.push(input[i]);
		}

		else {
			if (last_in == i - 1) { //리프노드인지 확인
				result += (st.size() - 1);
			}
			st.pop();
		}
	}

	cout << result << "\n";

	return 0;
}