[백준] 2504 괄호의 값 자바

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

2504번: 괄호의 값

 

1년 전에 한번에 풀었던 문제인데, 이제보니까 죽어도 모르겠어서 과거의 내 답지를 한번 보고

다시 풀었는 데 그래도 몇 번 틀렸습니다 ;ㅁ; (그래도 본인 골드1인데..)

 

반례가 많은 문제여서 심지어 문제를 읽어보면 문제에 반례가 적혀있습니다.

 

하여튼 핵심은 재귀함수를 사용해서 '(' 또는 '[' 에서 내부에 괄호가 있는 지 확인하는게 핵심입니다.

그리고 괄호가 올바른 지의 유무를 따지는 것은 스택을 사용해서 확인합니다.

 

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

public class 괄호의값 {

	static int n, ans = 0;
	static String str = "";
	static boolean[] visited = new boolean[31];
	static Stack<Character> stk = new Stack<>();

	// (()[[]])([])
	static int dfs(int idx, int val) {

		char c = str.charAt(idx);
		char goal;
		int sum = 0;
		int val2 = 0;

		visited[idx] = true;
		stk.add(c);

		if (c == '(')
			goal = ')';
		else
			goal = ']';

		for (int x = idx + 1; x < str.length(); x++) {

			char next = str.charAt(x);

			if (visited[x])
				continue;

			if (next == '(') {
				val2 = 2;
//				sum += dfs(x, val2);  다음 괄호의 모양에 따라 dfs를 사용하면 올바르지 못한 괄호같은 반례를 쳐낼 수가 없다 (올바르지 못한 괄호를 지나쳐버려서)
			} else if (next == '[') {
				val2 = 3;
//				sum += dfs(x, val2);
			}

			if (next == goal) { // ( [
				stk.pop();
				visited[x] = true;
				if (sum == 0) {
					return val;
				} else {
					return val * sum;
				}
			} 
			else { //else문으로 올바르지 못한 괄호까지 처리할 수 있게 해주어야 stack처리가 되어서 반례에 0이 나온다
				sum += dfs(x, val2);
			}
		}
		return sum * val;
	}

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		str = br.readLine();

		for (int x = 0; x < str.length(); x++) {
			if (!visited[x]) {
				int v = 0;
				if (str.charAt(x) == '(')
					v = 2;
				else if (str.charAt(x) == '[')
					v = 3;
				
				ans += dfs(x, v);
			}
		}

		if (stk.size() != 0)
			System.out.println(0);
		else
			System.out.println(ans);

	}
}