[백준] 26111번 Parentheses Tree C++ 문제풀이

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

26111번: Parentheses Tree

 

문제 풀이

처음에는 재귀를 이용해서 문제를 풀었는데, 입력 크기가 최대 10^7이기 때문에 당연히 시간초과가 떠버렸다.

자료구조 stack을 이용해서 문제를 풀려고 했으나, 깊이를 처리하지 못해 고민하던 중 다른 블로그 글의 도움을 받아 리프의 깊이는 현재 닫히지 않은 열린 괄호의 개수와 같다는걸 알게 되었다.

소스 코드

#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;
}