[프로그래머스] 괄호 변환 (2020 KAKAO BLIND RECRUITMENT)

문제 링크 : programmers.co.kr/learn/courses/30/lessons/60058

 

 

<전체적 알고리즘>

문제 자체에 알고리즘이 완벽하게 주어져 있다. 알고리즘이 주어져있지 않았다면 분명히 어려운 문제겠지만 문제에 알고리즘이 자세히 설명되어있기에 그냥 고민할 것 없이 그대로 구현하면 된다. 알고리즘이 그대로 적혀있기에 굳이 설명할 것 없이 넘어가겠다.

 

 

<올바른 괄호 문자열 확인 알고리즘>

전체적인 알고리즘은 그대로 구현하면 되지만 올바른 문자열인지 아닌지 판별하는 함수는 생각해 보아야 한다. 

 올바른 괄호 문자열 판별은 단순히 스택을 이용해서 알 수 있다. 열린 괄호일 때 stack에 넣어주고 닫힌 괄호일 때 stack에서 빼주면서 쌍을 만들어 준다. 모두 쌍이 만들어지면 올바른 괄호 문자열이다.

 

(코드에서는 stack을 이용하여 구현하였지만 사실 stack을 이용할 필요도 없다. 단순히 변수 count를 이용하여 열린괄호면 count++ 닫힌 괄호면 count--하며 변수하나만으로도 간단히 구현이 가능하지만 좀 더 직관적으로 설명하기 위해 stack을 이용했다.)

 

 

<전체 코드>

#include<iostream>
#include<stack>
#include<string>

using namespace std;

bool iscorrect(string u)    // 올바른 괄호 문자열인지 확인, 맞는 괄호 짝을 찾아줘야함
{
	stack<int> s;
    
	for (int i = 0; i < u.size(); i++)
	{
		if (u[i] == '(')s.push(u[i]);
		else 
		{
			if (s.empty())return false;   //닫힌괄호가 나왔는데 스택이 비어있으면 쌍이없음,,false
			s.pop();
		}
	}
	if (!s.empty())return false;   //짝을 다 찾아줬는데 아직 남아있는 괄호있으면 false,,
	return true;
}

string make_correct(string p)    //올바른 괄호 문자열 만드는 함수
{
	if (p.size() == 0)return "";
	string u = "";
	string v = "";
	
	int balanced = 0;
	int i = 0;
	for (; i < p.size(); i++)   //u 만들어주기
	{
		u += p[i];
		if (p[i] == '(')balanced++;
		else balanced--;

		if (balanced == 0)break;      // balanced가 0이되면 균형잡힌 괄호 문자열 완성
	}
	i++;
	for (; i < p.size(); i++)    // v만들어주기 
	{
		v += p[i];
	}
	
	if (!iscorrect(u))  //u가 올바른 괄호 문자열이 아니라면 
	{
		string result = "(";
		result+= make_correct(v);  //나머지 v에 대해 올바른 괄호 문자열 만들기
		result += ")";

		string tmp = u.substr(1, u.size() - 2);  //앞뒤 문자떼어버리기
		for (int i = 0; i < tmp.size() ;i++)   //문자들 뒤집기
		{
			if (tmp[i] == '(')tmp[i] = ')';
			else tmp[i] = '(';
		}
		
		return result + tmp;   //반환
	}
	else
	{
		string result=make_correct(v);  //v에 대해서 올바른 괄호 문자열 만들기
		return u + result;   // u랑 합쳐서 반환
	}
}

string solution(string p) {
    
    string answer = make_correct(p);
    return answer;
}

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.