[백준 02504] 괄호의 값 [Java]

문제

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

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

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

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

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

입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.

---

풀이

풀이 설명전에 문제 예제를 먼저 살펴보겠다.

(()[[]])([]) = (2 + [3])(3) = (2 + 3*3)(3) = 2*(2 + 3*3) + 2*3 = 2*2 + 2*3*3 + 2*3 = 28 와 같이 인수분해의 순서대로 곱을 누적하며 계산할 수 있다.

 

이를 풀이에 적용해보자.

입력값을 순차적으로 탐색하며, 왼쪽 괄호인 경우에는 push와 곱 누적만 해주면 된다.

만약, 오른쪽 괄호와 매칭되는 왼쪽 괄호가 없거나( stack.isEmpty() ), 올바르지 못한 괄호라면 더 이상 탐색할 필요가 없다. 

올바른 괄호라면 왼쪽 괄호를 대기열에서 pop하고, 원래 문자열의 이전 순서와 비교해 알맞는 순서에만 누적 곱을 결과에 더해주자. 누적곱을 결과에 더했다면, 현재의 올바른 괄호의 값만큼 누적곱을 나누어 다음 값에 대한 올바른 인수분해 순서를 보장해주자.

stack에는 왼쪽 괄호들의 대기열이다. 때문에 입력이 왼쪽 괄호만 주어진다면, 올바르지 못한 괄호열인지 판단이 불가능하다. 탐색이 종료된 후 stack이 비어있지 않다면, 결과를 0으로 변경해주자.

---

소스코드

보기

---

출처

2504번: 괄호의 값