[Baekjoon] 26111_Parentheses Tree

문제(출처: https://www.acmicpc.net/problem/26111)

---

< Parentheses Tree >

 

문제 풀이 

 

루트에서 모든 leaf node까지의 거리의 합을 구하라

 

* leaf node : ) 바로 앞에 (가 오면 leaf node이다.

* 루트에서 leaf node까지의 거리 == stack의 크기

 

my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class _26111_ { // Parentheses Tree

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		Stack<Character> stack = new Stack<>();
		long result = 0;

		String str = bf.readLine();
		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) == '(') {
				stack.add(str.charAt(i));
			} else {
				stack.pop();
				if (str.charAt(i - 1) == '(') {
					result += stack.size();
				}
			}
		}
		System.out.println(result);
	}
}

변수)
stack : '(' 저장하는 Stack 
result : 루트에서 모든 leaf node까지의 거리의 합
str : 입력값

 

입력값을 탐색하며 '('일 경우 stack에 저장하고, ')'일 경우 stack에서 pop 한다. 이때, ')' 바로 앞이 '('라면 leaf node라는 뜻이므로 stack의 크기를 result에 더한다.

---

---