백준 2504번 괄호의 값

문제 링크: https://www.acmicpc.net/problem/2504

사용한 알고리즘: stack, 재귀함수


 (, ), [, ] 4가지로 주어지는 괄호열이 옳은지 판단하고, (): 2, []: 3 의 값으로 계산하여 그 값을 출력하는 문제였습니다.

풀이과정은 다음과 같습니다.
(1) 기본적으로 stack<char>을 만들어 ' ( ' 와 ' [ ' 을 쌓거나 지워줄 것입니다. 이때 완성되는 괄호열들을 온전한 덩어리 별로 묶을 것입니다. 예를들어 괄호열이 " ([]())() 로 주어진다면,  " ([]()) " 부분과 " () " 부분으로 나누어 생각할 것입니다. 매 온전한 덩어리들의 처음 index를 StartPoint 로 저장해 주고, 온전한 덩어리라고 판단 될 시, StartPoint 부터 끝나는 지점까지의 온전한 덩어리의 값을 계산해 줄 것입니다.

(2) ' ( ' 이 들어오는 경우 stack에 쌓아주고, ' ) ' 이 들어오는 경우 stack 의 top 값이 ' ( ' 인 경우 () 가 완성되었다고 생각하고 stack의 top 값을 지워줍니다. 만약 ' ) '가 들어왔는데 stack의 top 값이 ' ( ' 가 아닌경우 이는 완전한 괄호열이 되지 않는 경우이므로 0 을 출력해주면 됩니다.  ' [ ' 와 ' ] ' 도 같은 방법으로 set에 쌓아주고 지워줍니다.

(3) 과정 2를 진행중 stack 이 empty 가 되는 경우 과정 1에서 언급한 온전한 덩어리로 묶어졌다는 뜻입니다. 이경우 과정(1)에서 언급한 것 처럼 StartPoint 부터 온전한 덩어리의 끝 index 까지 온전한 덩어리의 값을 계산해 주고 ( StartPoint = s, 끝 index = e 라고 합시다), 다음 index를 다시 다음 온전한 덩어리의 StartPoint 로 갱신해줍니다.

(4) 덩어리들의 값은 Value 라는 재귀 함수를 짜서 구해주었습니다. 이 함수에 index s, e가 들어오는 경우
  1.  s+1 = e 인 경우 '()' 또는 '[]' 라는 뜻이됩니다. 전자의 경우 2를 후자의 경우 3을 return합니다.
  2. 위경우가 아닌, s ~ e 사이에 또 다른 괄호들이 있는 경우 입니다. s 번째 괄호 (이는 온전해야 하므로 시작점인 s는 ' ( ' 또는 ' [ ' 입니다.) 의 짝을 ( index k ) 를 찾아줍니다. 우리는 ' ( ' 인 경우를 생각해 보겠습니다.
  3. 위에서 찾은 k가 k!=s+1인 경우 s~k 사이에 또 다른 괄호들이 있다는 의미이므로 ( 우리는 ' ( ' 인 경우를 생각하기로 했으므로 )   2 ( ()값 ) * Value(i+1, k-1) (그 안의 또 다른 괄호들의 값) 을 취해줍니다.
  4. 이후 k!=e 인 경우, k ~ e 사이에 또다를 괄호가 있다는 뜻이므로,
3에서 구한 값 + Value(k+1 , e) 를 return 해줍니다.

(5) 입력되는 괄호들을 모두 과정 (1)~(5) 로 돌려줍니다.

stack을 써서 온전한 괄호를 찾는다는 개념은 많이 쓰이나, 이 온전한 괄호 값을 재귀적으로 구하는 것이 조금 까다로운 문제였습니다.