[Baekjoon 26111] Parentheses Tree - JAVA

[Silver II] Parentheses Tree - 26111

문제 링크

성능 요약

메모리: 59836 KB, 시간: 356 ms

분류

자료 구조, 스택, 문자열

문제 설명

A rooted ordered tree $T$ can be expressed as a string of matched parentheses $p(T)$. The string representation $p(T)$ can be defined recursively. As a base case, a tree consisting of a single node is expressed by a pair of parentheses (). When a rooted ordered tree $T$ consists of a root node and $k$ ordered subtrees $T_1, T_2, \dots , T_k$ having their roots as child nodes of the root node, the string representation $p(T)$ is defined as follows:

$p(T) ≔$ ( +p(T1)+p(T2)+⋯+p(Tk)+$+ p(T_1) + p(T_2) + \cdots + p(T_k) +$ )

In the above expression, the operator +$+$ means the concatenation of two strings. The figure below shows two examples of rooted ordered trees. The string representations $p(T_L)$ and $p(T_R)$ are ((()()())()) and (()((()(()))())), respectively.

The distance from the root node to a leaf node is defined as the number of edges to be traversed to reach the leaf from the root. In the figure above, the root nodes are colored in blue, and the distances from the root node to all leaf nodes are shown. For trees $T_L$ and $T_R$ the sum of the distances from the root to all leaf nodes are $7$ and $10$, respectively.

Given a string of matched parentheses representing only one rooted ordered tree, write a program to output the sum of the distances from the root of the tree to all leaf nodes.

입력

Your program is to read from standard input. The input consists of one line containing a string of matched parentheses which represents only one rooted ordered tree. The input does not contain any characters other than parentheses, and the length of string is at least $2$ and no more than $10^7$.

출력

Your program is to write to standard output. Print exactly one line. The line should contain the sum of the distances from the root of the rooted ordered tree to all leaf nodes.

문제 풀이

한글로 문제를 요약, 정리하면 아래와 같다.

루트 노드가 있는 유한 트리를 괄호로 나타낼 수 있다.

괄호로 나타낸 트리를 다시 원래 트리로 변환할 수 있고, 루트에서 각 리트 노드까지의 거리 합을 구해야 한다.

문제를 풀때 아래 내용들을 생각하며 풀었다.

문자열 '(' 와 ')'가 쌍으로 주어졌는지, 입력이 $10^7$까지 가능하다.

루트 노드에서 각 리프 노드까지의 거리들을 모두 합한 값이 출력으로 나와야 한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();

        int chk = -1, cnt = 0;
        long ans = 0;

        for (int idx = 0; idx < str.length(); ++idx) {
            char c = str.charAt(idx);
            if (c == '(') {
                chk = idx;
                cnt++;
            } else {
                cnt--;
                if (chk == (idx - 1)) {
                    ans += cnt;
                }
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(Long.toString(ans));
        bw.flush();
    }
}

코드 풀이