백준 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을 써서 온전한 괄호를 찾는다는 개념은 많이 쓰이나, 이 온전한 괄호 값을 재귀적으로 구하는 것이 조금 까다로운 문제였습니다.

	#include <bits/stdc++.h>
	using namespace std;
	string St;
	stack<char> Waite;
	int ans;
	int StartP = -1;
	bool Fail;
	int Value(int s, int e){
	int temp = 0;
	if(s+1 == e){
	if(St[s]=='(') return 2;
	else return 3;
	}
	char now, want;
	if(St[s]=='('){
	now = '(';
	want = ')';
	temp = 2;
	}
	else{
	now = '[';
	want = ']';
	temp = 3;
	}
	int CheckP;
	int num = 1;
	for (int i = s+1; i <= e; ++i){
	if(St[i]==now) num++;
	else if(St[i]==want){
	num--;
	if(num==0){
	CheckP=i;
	break;
	}
	}
	}
	if(s+1!=CheckP) temp*=Value(s+1,CheckP-1);
	if(CheckP!=e) temp+=Value(CheckP+1,e);
	return temp;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> St;
	for (int i = 0; i < St.size(); ++i){
	if(St[i]=='('||St[i]=='['){
	if(Waite.empty()) StartP=i;
	Waite.push(St[i]);
	}
	else{
	if(Waite.empty()){
	Fail = true;
	break;
	}
	if(St[i]==']'){
	if(Waite.top()=='[') Waite.pop();
	else Waite.push(St[i]);
	}
	else{
	if(Waite.top()=='(') Waite.pop();
	else Waite.push(St[i]);
	}
	if(Waite.empty()) ans += Value(StartP,i);
	}
	}
	if(!Waite.empty()) Fail = true;
	if(Fail) cout << 0 << '\n';
	else cout << ans << '\n';
	return 0;
	}

view raw BOJ 2504.cpp hosted with ❤ by GitHub