[PS] 백준 2504 : 괄호의 값(JAVA)

문제

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

2504번: 괄호의 값

 

---

풀이

자료구조 스택을 활용하여 풀이

 

접근법

temp라는 임시 변수를 활용.

 

여는 괄호의 경우

1. Stack.Push()
2. temp *= 2 혹은 temp *=3

→ 여는 부분에서 곱하거나 더할 값을 temp변수에 누적

 

닫는 괄호의 경우

1. Stack.isEmpty() 체크
2. 각각의 괄호에 따라 결과값에 temp값 누적 및 temp값 감소
   1. temp /= 3 or temp /= 2

 

---

소스코드

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

    //BOJ_2504 괄호의 값
    public class Main {
        static int N, M, res;
        public static void main(String[] args) throws IOException {

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

            String input = br.readLine();

            Stack<Character> stack = new Stack<>();

            int temp = 1;
            for(int i=0; i<input.length(); i++) {
                char idx = input.charAt(i);

                if(idx == '(') {
                    stack.push(idx);
                    temp *= 2;
                }
                if(idx == '[') {
                    stack.push(idx);
                    temp *= 3;
                }

                else {
                    //닫는 괄호의 경우
                    if(stack.isEmpty()) {
                        System.out.println(0);
                        return;
                    }

                    if (idx == ')') {
                        if (stack.peek() == '(') {

                            if (input.charAt(i-1) == '(') {
                                res += temp;
                            }

                            stack.pop();
                            temp /= 2;

                        } else {
                            System.out.println(0);
                            return;
                        }
                    } else if (idx == ']') {
                        if (stack.peek() == '[') {

                            if (input.charAt(i-1) == '[') {
                                res += temp;
                            }
                            temp /= 3;
                            stack.pop();
                        } else {
                            System.out.println(0);
                            return;
                        }
                    }
                }
            }

            if(!stack.isEmpty()) {
                System.out.println(0);
                return;
            }
            
            System.out.println(res);

        }
    }

 

---

반례

37%
Input
(((()))(([])))(([[]]))

Answer : 81
output : 0

--------------------------------
43%
Input
()((((()

answer : 0

 

---

정리

올바른 괄호와 관련된 문제는 대부분 스택으로 풀었기 때문에 해당 문제 또한 스택 자료구조로 접근하긴 했지만 생각보다 곳곳에서 반례가 자꾸 터져 곤란했던 문제.

풀기 전 구상한 로직에 대한 정리 및 논리적으로 검증하는 시간을 가지고 코드를 써내려갔다면 조금 더 빠르게 해답에 접근하지 않았을까 함.

자료구조관련 문제는 계속 계속 풀어봐야 할 것 같음….