알고리즘 단계별로 풀어보기 : BOJ-2504(괄호의값)

문제(출처)

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 

만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. 

X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. 

‘()’ 인 괄호열의 값은 2이다.

‘[]’ 인 괄호열의 값은 3이다.

‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.

‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.

올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자.  

‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로  ‘(()[[ ]])’의 괄호값은 2×11=22 이다. 

그리고  ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다. 

입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 

단 그 길이는 1 이상, 30 이하이다.

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 

만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다. 

예제 입력

(()[[]])([])

예제 출력

28

내 풀이

package date_20190128;

import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

import java.util.Stack;

public class BOJ_2504 {

//  입력 되는 괄호가 올바른지 확인하고 연산한다.

//  () 는 2

//  [] 는 3

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

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

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String str = br.readLine();

        Stack<String> s = new Stack<>();

        boolean check = true;

        int sum = 0;

        int temp = 1;

        for (int i = 0; i < str.length(); i++) {

            if (str.charAt(i) == '(') {

                s.push("(");

                temp *= 2;

            } else if (str.charAt(i) == '[') {

                s.push("[");

                temp *= 3;

            } else if (!s.empty() && str.charAt(i) == ')') {

                if(str.charAt(i -1 ) == '(') {

                    sum += temp;

                }

                if (s.peek().equals("(")) {

                    s.pop();

                } else {

                    check = false;

                    break;

                }

                temp /= 2;

            } else if (!s.empty() && str.charAt(i) == ']') {

                if(str.charAt(i -1 ) == '[') {

                    sum += temp;

                }

                if (s.peek().equals("[")) {

                    s.pop();

                } else {

                    check = false;

                    break;

                }

                temp /=3;

            } else {

//              System.out.println("에러 발생");

                check = false;

            }

        }

        if (check && s.empty()) {

            bw.write(String.valueOf(sum));

        } else {

            bw.write("0");

        }

        bw.close();

    }

}

내 풀이 해석

'(', '[' 두 괄호만 스택에 저장합니다.

'('를 만나면 2를 곱해주고  '['를 만나면 3을 곱해줍니다. - 중첩 된 만큼 미리 곱해줍니다.

')', ']' 닫힌 괄호를 만나면 스택이 비어있는지 확인하고 이전 값이 쌍이 과는 열린 괄호가 맞는지 확인합니다.

맞다면 임시 값을 총합에 더해주고 현재 괄호를 꺼냅니다.

만약 괄호가 쌍이 아니면 올바른 괄호들이 아니므로 0을 출력합니다.

중첩 된 값 중 1단게를 줄이기 위해 해당 괄호에 해당하는 수를 나누어 줍니다.

스택에 남아있는 데이터가 있으면 올바르지 않은 괄호 이므로 0을 출력합니다.

아쉬운 점

스택 활용법에 대해서 아직 잘 모르는거 같습니다.

이전 문제인 9012(괄호)를 다른 분들은 어떻게 풀었는지 확인해보았고 응용해서 풀었습니다.

어렵다고 생각한 문제입니다.

디버깅을 하면서 풀었습니다.

학습/검색

참고