[伯俊]#1662圧縮

質問する

非圧縮文字列Sが与えられると、これらの文字列の一部はK(Q)に圧縮され得る.Kは整数であり、Qは0ビット以上の文字列である.このQは文字列がK回繰り返されるという意味です.圧縮文字列が指定されている場合は、ライターが文字列を再解凍します.

入力

1行目は圧縮された文字列Sを入力する.Sの長さは最大50です.文字列は、(,)と0-9の間の数値で構成されます.

しゅつりょく

最初の行は、非圧縮文字列の長さを出力します.この値はint範囲です.

入力例1

33(562(71(9)))

サンプル出力1

19

に答える

この問題はbfs(幅優先探索)アルゴリズムで解くことができる.

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

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        Stack<Integer> stack = new Stack<>();
        int[] close = new int[input.length()];

        for(int i=0; i<input.length(); i++) {
            char c = input.charAt(i);

            if(c=='(') {        //괄호가 열리면 idex를 스택에 넣음
                stack.push(i);
            }

            else if(c==')') {
                close[stack.pop()] = i;   //괄호가 닫히면 열린괄호의 idex에 닫히는 괄호의 idex 값 저장
            }
        }

        System.out.println(sol(input, close, 0, input.length()));
    }

    public static int sol(String str, int[] close, int start, int end) {
        int ans = 0;

        for(int i=start; i<end; i++) {
            char c = str.charAt(i);

            if(c=='(') {
                ans += sol(str, close, i+1, close[i])*(str.charAt(i-1)-'0');
                ans--;    //괄호가 열리면 앞의 수만큼 곱하고 그 수는 사라지기 때문에 1을 빼줌
                i = close[i];
            }

            else
                ans++;
        }

        return ans;
    }
}