[백준]#1662 압축

문제

압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이다. 압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오.

입력

첫째 줄에 압축된 문자열 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;
    }
}