[알고리즘] 백준 - 괄호의 값

백준 - 괄호의 값

내 풀이

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

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

        System.out.println(solve(0, str.length()-1));

    }

    private static int solve(int start, int end) {
        if (str.substring(start, end+1).equals("")) {
            return 1;
        }

        Stack<Integer> stack = new Stack<>();
        int ans = 0;
        for (int i = start; i <= end; i++) {
            if (stack.size() == 1) {
                if ( (str.charAt(stack.peek()) == '(' && str.charAt(i) == ')')) {
                    ans += 2 * solve(stack.pop()+1, i-1);
                    continue;
                } else if (str.charAt(stack.peek()) == '[' && str.charAt(i) == ']') {
                    ans += 3 * solve(stack.pop()+1, i-1);
                    continue;
                }
            }
            if (str.charAt(i) == '(' || str.charAt(i) == '[') {
                stack.add(i);
            } else if (stack.size() > 0 && (str.charAt(stack.peek()) == '(' && str.charAt(i) == ')'
                || str.charAt(stack.peek()) == '[' && str.charAt(i) == ']')) {
                stack.pop();
            } else {
                System.out.println(0);
                System.exit(0);
            }

        }
        if (stack.size() > 0) {
            System.out.println(0);
            System.exit(0);
        }
        return ans;
    }
}

다소 복잡하게 풀었다. 우선 전체 스트링에 대해 for문을 돌면서 stack이 맞아떨어져서 올바른 괄호열이면 그만큼 구분해서 재귀에 들어가게 했다 (단 양측의 괄호는 제거하고 괄호에 따라 점수를 곱한다). 그리고 나머지 부분에 대해 또 재귀를 돌리고해서 점수를 더하는 방식이다.

주어지는 괄호열의 길이가 1이상이므로 만약 함수에서 str의 길이가 0이라면 이전에 길이가 2인 올바른 괄호열이어서 양측을 제거하고 들어온 함수이다. 따라서 1을 반환하면 된다.

자바의 substring