백준 2800 - 괄호 제거

 

 

문제 설명

어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.

하지만, 1+(2*3, ((2+3)*4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.

괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.

예를들어 (2+(2*2)+2)에서 괄호를 제거하면, (2+2*2+2), 2+(2*2)+2, 2+2*2+2를 만들 수 있다. 하지만, (2+2*2)+2와 2+(2*2+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.

어떤 식을 여러 쌍의 괄호가 감쌀 수 있다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 주어진 식에서 괄호를 적절히 제거하여 만들 수 있는 서로 다른 식을 출력하면 된다.

이때 괄호는 알맞은 짝끼리만 제거할 수 있다.

(0/(0))

여기서 2번째 괄호과 4번째 괄호는 짝이 아니기 때문에 제거할 수 없다.

 

해당 문제는 DFS를 통해 풀 수 있다.

문자를 하나씩 살펴보면어 닫는 괄호가 등장하면 이와 맞는 짝을 제거한 경우와 그렇지 않은 경우 각각 DFS를 진행하면 된다.

우선 제거하지 않은 경우는 현재 문자열에 마지막 문자를 추가하면 되기 때문에 간단하다.

current += str[depth];
DFS(depth + 1, current);

 

문제는 괄호를 제거하는 경우인데 현재 처리할 닫는 괄호와 짝을 찾는 것이다.

일반적인 올바른 괄호를 찾는 로직(스택을 이용)은 올바른 괄호짝이 아닐 경우가 있다.

따라서 이를 처리하기 위해서는 닫는 괄호의 개수를 세면 된다. 

현재 문자열의 오른쪽 끝부터 순회하며 닫는 괄호의 개수가 0인 상태에서 여는 괄호를 만난다면 지금 괄호와 짝이 맞게 된다.

예를 들어 보자.

(0/(0))

가장 마지막 괄호를 제거하려고 한다.

일반적인 괄호를 체크하는 방법으로는 왼쪽으로 진행하다 '/' 오른쪽에 있는 여는 괄호를 만난다면 괄호를 제거하려 할 것이다.

하지만 해당 여는괄호는 오른쪽에서 두 번째 닫는 괄호와 짝이기 때문에 제거할 수 없고 가장 왼쪽에 있는 괄호를 제거해야 한다.

따라서 여는 괄호를 만나기 전까지 마주친 닫는 괄호의 개수를 세고 만약 여는 괄호를 만났을 때 닫는 괄호의 개수가 0이 아니라면 하나씩 줄이면 된다.

if (current[i] == '(')
{
    if (closeCnt != 0)
    {
        closeCnt--;
        continue;
    }
}
else if (current[i] == ')')
{
    closeCnt++;
}

만약 닫는 괄호가 0개일 때 여는 괄호를 만나면 해당 괄호랑 짝이 맞기 때문에 이를 제거한 문자열을 만들어 다음 분기를 진행하면 된다.

// 제거하는 경우
sub = current.substr(i + 1, current.length() - i - 1);
auto frontStr = current.substr(0, i);
frontStr += sub;
DFS(depth + 1, frontStr);

 

한 가지 주의할 점은 서로 다른 수식을 출력해야 하기 때문에 완성한 수식을 set으로 저장해야 한다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;

string str;
set<string> answers;

void DFS(int depth, string current)
{
	if (depth == str.length())
	{
		if (current != str)
		{
			answers.insert(current);
		}
		return;
	}

	// 제거하는 경우
	if (str[depth] == ')')
	{
		string sub = "";

		int i = current.length() - 1;
		int closeCnt = 0;
		for (; i >= 0; i--)
		{
			if (current[i] == '(')
			{
				if (closeCnt != 0)
				{
					closeCnt--;
					continue;
				}

				sub = current.substr(i + 1, current.length() - i - 1);
				break;
			}
			else if (current[i] == ')')
			{
				closeCnt++;
			}
		}

		auto frontStr = current.substr(0, i);
		frontStr += sub;
		DFS(depth + 1, frontStr);
	}

	// 아닌 경우
	current += str[depth];
	DFS(depth + 1, current);
}

int main()
{
	INPUT_OPTIMIZE;
	
	cin >> str;

	string temp;
	DFS(0, temp);

	for (auto& ans : answers)
	{
		cout << ans << "\n";
	}

	return 0;
}

---