質問する

新しい開発者としてKakaoに入社したConは、他の開発者が作成したソースコードを分析し、問題を発見して修正するように、先輩の開発者から作業任務を受けた.ソースコードをコンパイルしてログを表示すると、ほとんどのソースコードのカッコがペアではない形式で記述されているため、エラーが発生します.
変更が必要なソースファイルが多すぎるため、コンソールは次のプログラムの開発を検討しています.
用語定義
文字列が「(」と「)」のみで構成され、「(」の数と「)」の数が同じである場合は、バランスカッコ文字列と呼ばれます.
「(」と「)」のカッコが一致している場合は、正しいカッコ文字列と呼ばれます.
たとえば、文字列「()」()は、バランスのとれたカッコ文字列ですが、有効なカッコ文字列ではありません.
逆に、文字列(()()など)は、バランスのとれたカッコ文字列であり、正しいカッコ文字列でもあります.
「(」と「)のみからなる文字列wがバランスの取れた括弧文字列である場合、以下の手順で正しい括弧文字列に変換できます.

入力

が空の文字列である場合、空の文字列が返されます.

文字列wを2つの「バランスカッコ」u,vに分割します.ただし、uは「バランスカッコ文字列」に区切ることはできず、vは空の文字列であってもよい.

文字列uが「正しい括弧文字列」である場合、ステップ1から文字列vの操作を開始します.
3-1. 実行後、文字列をuに接続して返します.

文字列uが「正しいかっこ文字列」でない場合は、次の手順に従います.
4-1. 「(」を最初の文字として空の文字列に追加します.
4-2. 文字列vに対して再帰操作を行い、ステップ1から文字列を接続する.
4-3. ')'貼り付け直します.
4-4. uの最初の文字と最後の文字を削除し、残りの文字列のカッコ方向を逆さまにして後ろに貼り付けます.
4-5. 生成された文字列を返します.

バランスカッコ文字列pをパラメータとして指定した場合、解関数を完了し、指定したアルゴリズムを実行し、正しいカッコ文字列に変換した結果を返します.
パラメータの説明
pは「(」と「」)のみからなる文字列であり、長さが2または1000より大きい偶数である.
文字列pの「(」と「)」は常に同じである.
pが有効なカッコ文字列である場合は、それを返すことができます.

コード#コード#

// 괄호 변환
// https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

#include <string>
#include <vector>
#include <iostream>

using namespace std;

bool checkBalanace(string &s, char target1, char target2) {
	int count_1 = 0;
	int count_2 = 0;
	for (char c : s) {
		if (c == target1) ++count_1;
		else if (c == target2) ++count_2; // else 로 할 수 있지만 가독성을 위해. -> 올바른 판단인가 ?
	}

	return count_1 == count_2;
}

bool checkRight(string s, char target, char pair) {
	if (s.empty())
		return true;

	int last_idx = s.rfind(target);
	if (last_idx == (s.size() - 1))
		return false;

	if (s[last_idx + 1] == pair) {
		s.erase(last_idx, 2);
		return checkRight(s, target, pair);
	}
}

string reverseDir(string s, char dir1, char dir2) {
	for (char& c : s) {
		c = (c != dir1) ? dir1 : dir2;
	}

	return s;
}

string solution(string p) {
	if (p.empty()) return "";

	char check_char1 = '(';
	char check_char2 = ')';
	string answer = "";

	for (int i = 2; i <= p.size(); i += 2) {
		string u = p.substr(0, i);
		string v = (i == p.size()) ? "" : p.substr(i);
		if (checkBalanace(u, check_char1, check_char2)) {
			if (checkRight(u, check_char1, check_char2)){
				answer = u + solution(v);
			} else {
				u = u.erase(0, 1);
				u = u.erase(u.size() - 1, 1);
				answer = check_char1 + solution(v) + check_char2 + reverseDir(u, check_char1, check_char2);
			}
			break;
		}
	}

	return answer;
}

int main()
{
	cout << solution("(()())()") << endl;   // "(()())()"
	cout << solution(")(") << endl;         // "()"
	cout << solution("()))((()") << endl;   // "()(())()"
	//cout << solution("()))((()") << endl;
}

の均一な括弧配列uまで探した.

uが正しい場合、vの再帰関数によって正しい配列が与えられる.

uが正しくない場合、「(」および「)」で正しいv配列を再帰的に作成し、最初の要素と最後の要素を除去するuカッコの方向を変更します.