프로그래머스 - 괄호 변환(C++)

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/60058

문제 난이도

Lv 2

문제 접근법

문제를 잘 읽고 구현하는 DFS 문제

통과 코드

#include <string>
#include <vector>
#include <stack>

using namespace std;

bool isRightString(string p) {
	stack<char> s;
	for (int i = 0; i < p.size(); i++) {
		if (p[i] == '(') {
			s.push(p[i]);
		}
		else {
			if (!s.empty()) s.pop();
			else if (s.empty()) s.push(p[i]);
		}
	}
	if (!s.empty()) return false;
	return true;
}

string dfs(string s) {
	if (s.empty()) return "";
	string ans = "",u="",v="";
	int ch = 0;
	bool flag = false;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == ')' && !flag) {
			u += s[i];
			ch--;
		}
		else if(s[i] == '(' && !flag){
			u += s[i];
			ch++;
		}
		else if (flag) {
			v += s[i];
		}
		if (ch == 0) flag = true;
	}

	if (isRightString(u)) {
		ans = u + dfs(v);
	}
	else {
		ans = "(";
		ans += dfs(v);
		ans += ')';
		string tmp = "";
		for (int i = 1; i < u.size()-1; i++) {
			if(u[i] == ')') u[i] = '(';
            else u[i] = ')';
            tmp += u[i];
		}
		ans += tmp;
	}
	return ans;
}

string solution(string p) {
	string answer = "";
	if (isRightString(p)) return p;
	answer = dfs(p);
	return answer;
}

피드백

문제 중 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 라는 지문에서 방향을 뒤집어서 뒤에 붙인다는게 뒤에서부터 뒤집는다는 뜻이 아니였다.
( -> ) , ) -> (
괄호의 방향을 뒤집으라는 이야기였다. 만약 이 지문을 잘못이해했다면 테스트케이스 12부터 쫙 틀릴 것이다.