백준 1662번 압축 (JAVA)

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

1662번: 압축

 

저는 재귀를 이용해 문제를 해결하였습니다.

해당 문자를 사용했는지 안했는지를 체크하고 안 했다면 cnt(결과 길이)값을 늘립니다.

'(' 라면 앞의 숫자를 빼고 cnt를 줄입니다. (앞의 숫자는 길이로 들어가지 않고 곱셈에 활용되기 때문입니다.)

앞의 숫자 * 재귀 함수를 통해 괄호 안에 있는 결과를 가져오고 곱합니다.

')' 라면 지금 cnt를 리턴하여 문제를 해결하였습니다.

 

package BOJ.etc;

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

public class BOJ_1662 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String command = br.readLine();
        boolean[] visited = new boolean[command.length()];
        int length = dfs(command,0,visited);

        System.out.println(length);
    }
    private static int dfs( String command , int index , boolean[] visited){
        int cnt = 0;
        for(int i = index ; i < command.length() ; i++){
            char ch = command.charAt(i);
            if(ch == '(' && !visited[i]){
                visited[i] = true;
                int num = command.charAt(i-1) - '0';
                cnt--;
                cnt += num * dfs(command,index+1,visited);
                continue;
            }
            if(ch == ')' && !visited[i]){
                visited[i] = true;
                return cnt;
            }
            if(!visited[i]){
                visited[i] = true;
                cnt++;
            }
        }
        return cnt;
    }
}