[백준] 2504 괄호의 값 자바

[백준] 2504 괄호의 값 자바

https://www.acmicpc.net/problem/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 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); } }

from http://rootcoder.tistory.com/35 by ccl(A) rewrite - 2021-12-28 00:27:49