[BOJ] 28709 - 와일드카드 괄호 문자열 | C++

문제

28709번: 와일드카드 괄호 문자열

 

 

분석

 

괄호의 쌍이 맞도록 문자열을 처리하는 문제입니다.

얼핏 보면 9012 - 괄호 와 같은 스택 문제처럼 보이기도 합니다만, '*' 문자를 '(', ')'로 이루어진 길이 0 이상의 문자열로 대체할 수 있다는 강력한 조건이 붙어 있습니다.

원하는 길이의 문자열을 붙일 수도 있고, 심지어 붙이지 않을 수도 있기 때문에 '*' 문자열이 단 하나라도 존재한다면 항상 올바른 괄호 문자열로 만들 수도 있겠다는 생각이 들 정도입니다.

 

()*)())
()*))))
()*()
(())*(())

 

예를 들어 위와 같은 문자열은 전부 올바른 괄호 문자열로 바꿀 수 있는 문자열입니다.

 

하지만 '*'가 등장하더라도 올바른 문자열을 만드는 것이 불가능한 경우가 존재합니다.

바로 예제에서도 주어진

())*(())

 

위와 같은 경우인데, '*'가 등장하기 전에 이미 유효하지 않은 문자열 "())"이 등장했기 때문에, 그 뒤에 어떤 문자열을 붙인다고 하더라도 유효한 문자열을 만드는 것은 불가능합니다.

 

반대로

(())*(()

 

위와 같은 문자열 역시 유효한 문자열을 만들 수 없습니다. 

'*'가 마지막으로 등장한 이후에 유효하지 않은 문자열 "(()"이 등장했기 때문에, 앞에 어떤 문자열을 붙인다고 하더라도 유효한 문자열을 만들 수 없습니다.

 

즉

• 문자열을 앞에서부터 읽어나갔을 때, 한 번이라도 '('의 개수보다 ')'의 개수가 많아지는 시점이 존재한다면 그 문자열은 올바른 괄호 문자열로 바꿀 수 없다.
• 문자열을 뒤에서부터 읽어나갔을 때, 한 번이라도 ')'의 개수보다 '('의 개수가 많아지는 시점이 존재한다면 그 문자열은 올바른 괄호 문자열로 바꿀 수 없다.
• '?' 문자열은 앞에서부터 읽을 때는 '('로, 뒤에서부터 읽을 때는 ')'로 치환하여 위 제약 조건을 최대한 완화한다.
• 위 제약 조건은 와일드카드 문자열 '*'이 등장하면 해제된다.

이렇게 정리할 수 있겠습니다.

 

 

풀이 과정

	int open = 0, close = 0, question = 0, wildcard = 0;
	for (const auto& c : s | views::reverse) {
		if (c == ')') ++open;
		if (c == '(') {
			if (!wildcard && open + question <= close) return false;
			++close;
		}
		if (c == '?') ++question;
		if (c == '*') ++wildcard;
	}

 

먼저 문자열을 역순으로 순회하며, 한 번이라도 ')'의 개수보다 '('의 개수가 많아지는 시점이 있는지 검사하였습니다.

상술했듯 '?' 문자는 ')' 문자로 취급하여 제약 조건을 완화해 주었습니다.

 

	open = 0, close = 0, question = 0, wildcard = 0;
	for (const auto& c : s) {
		if (c == '(') ++open;
		if (c == ')') {
			if (!wildcard && open + question <= close) return false;
			++close;
		}
		if (c == '?') ++question;
		if (c == '*') ++wildcard;
	}

 

그리고 앞에서부터 순회하며, 한 번이라도 '('의 개수보다 ')'의 개수가 많아지는 시점이 있는지 검사하였습니다.

마찬가지로 '?' 문자는 '(' 문자로 취급해 주었습니다.

 

if (wildcard) return true;

 

이제 와일드카드 문자열 '*'이 한 번이라도 등장한다면, 반드시 올바른 괄호 문자열을 만들 수 있다고 생각해도 무방합니다.

 

다음으로 와일드카드 문자열이 하나도 등장하지 않은 경우를 처리해 보겠습니다.

와일드카드 문자열이 하나도 없으므로, 문자열은 '(', ')', '?'로만 이뤄져 있습니다. 따라서 '('의 개수와 ')'의 개수가 같아야 하며, 차이가 난다면 '?' 문자로 보정해 주면 됩니다.

 

	int convert = static_cast<int>(s.length() / 2) - open;
	int st = 0;
	for (int i = 0; i < s.length(); ++i) {
		if (s[i] == '(') ++st;
		if (s[i] == ')') --st;
		if (s[i] == '?') {
			if (convert) {
				--convert;
				++st;
			}
			else --st;
		}
	}
	if (st) return false;
	return true;

 

'(' 문자의 개수는 문자열의 길이 / 2가 되어야 합니다. ')' 역시 마찬가지입니다. 

convert 변수는 '?' 문자를 몇 개나 '('로 바꿔야 하는지 저장하는 변수입니다. open 변수에 '(' 개수가 저장되어 있으므로 convert 변수에는 바꿔야 할 남은 '(' 문자의 개수가 들어 있게 됩니다.

 

문자열을 순회하며 '?' 문자가 등장하면 먼저 convert번 만큼 '(' 문자로 교체해주고, convert가 0이 되면 ')' 문자로 교체해 주면 됩니다.

open이 지나치게 커서, 즉 '(' 문자가 문자열에 지나치게 많아서 convert가 처음부터 0 이하로 내려가게 되면 'st' 변수가 0이 되지 않아 false를 리턴하게 됩니다. 문자열을 순회한 이후 st가 정확히 0이 되어야 true를 리턴합니다.

 

소스 코드

#include <iostream>
#include <string>
#include <ranges>
#define fastip std::cin.tie(nullptr)
#define sws std::ios::sync_with_stdio(false)
#define inf 987654321
#define ll long long
#define endl "\n"
using namespace std;

bool search(const string& s)
{
	int open = 0, close = 0, question = 0, wildcard = 0;
	for (const auto& c : s | views::reverse) {
		if (c == ')') ++open;
		if (c == '(') {
			if (!wildcard && open + question <= close) return false;
			++close;
		}
		if (c == '?') ++question;
		if (c == '*') ++wildcard;
	}
	open = 0, close = 0, question = 0, wildcard = 0;
	for (const auto& c : s) {
		if (c == '(') ++open;
		if (c == ')') {
			if (!wildcard && open + question <= close) return false;
			++close;
		}
		if (c == '?') ++question;
		if (c == '*') ++wildcard;
	}

	if (wildcard) return true;
	int convert = static_cast<int>(s.length() / 2) - open;
	int st = 0;
	for (int i = 0; i < s.length(); ++i) {
		if (s[i] == '(') ++st;
		if (s[i] == ')') --st;
		if (s[i] == '?') {
			if (convert) {
				--convert;
				++st;
			}
			else --st;
		}
	}
	if (st) return false;
	return true;
}

int main()
{
	fastip; sws;

	int t; cin >> t;
	while (t--) {
		string s; cin >> s;
		if (search(s)) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
}

 

GitHub - SH4MDEL/boj-algorithm: Solving Baekjoon Online Judge (https://www.acmicpc.net/)

 

위 리포지토리에서 전체 소스코드를 확인하실 수 있습니다.

감사합니다.