2024 - 08- 05 C++ 코딩테스트 10주완성 D+26

백준 4949 문제 : 균형잡힌 세상

 

대괄호 "[ ]" 와 소괄호 "( )" 가 있다.

 

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

 이 조건을 만족하면 "yes" 를 출력

 

만족하지 못하면 "no" 를 출력한다.

입력

각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.
입력의 종료조건으로 맨 마지막에 온점 하나(".")가 들어온다.

 

출력

 

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

 

실습코드

 

#include <bits/stdc++.h>

using namespace std;

//1. 변수목록
//소괄호의 수를 체크할 스택 sbk
//대괄호의 수를 체크할 스택 lbk
//입력받을 문자열 str
vector<char> m_vector;

char str[104];
bool isflag = true;

void StackList(char a)
{
	if (a == '(' || a == ')' || a == '[' || a == ']')
	{
		m_vector.push_back(a);
	}

}

int main()
{
	//2.알고리즘
	//2-1. 무한루프로 반복문
	//2-2. 문자열을 입력받는다. ( 문자열이 . 일시 break)
	//2-3. 문자열의 길이만큼 반복문
	//2-3-1. ([]) -> ( 스택 -> [ 스택 -> ] push -> 만약 [] 사이즈가 0일경우 isflag true
	while (true)
	{
		cin.getline(str,100,'.');		

		for (char i : str)
		{
			StackList(i);
		}

		vector<char> r_vector;

		if (m_vector.size() % 2 != 0)
			isflag = false;

		else
			for (int i = m_vector.size()/2 ; i < m_vector.size(); i++)
			{				
				r_vector.push_back(m_vector.back());
				m_vector.pop_back();
			}
		
		for (int i = 0; i < r_vector.size(); i++)
		{
			r_vector.reserve(r_vector.size());
			char a;

			if (m_vector[i] == '(')
				a = ')';

			else
				a = ']';

			if (a != r_vector[i])
				isflag = false;
		}
		

		if (isflag)
			cout << "yes" << endl;

		else
			cout << "no" << endl;
	}
}

 

처음에는 두개의 스택으로 소괄호 "( )" 와 대괄호 "[ ]" 의 조합마다 Pop Push를 하여주어 출력을 하려고 하였으나,

 

예를 들어 "( [ ) ] " 라는 한쌍이 생길 경우에는 Yes가 되어버린다...

 

그래서 생각해낸게 괄호만 받은 Vector를 반으로 잘라 그 두개가 같으면 Yes 아니면 No라고 출력하려고 하였으나..

 

무조건 반으로 잘라야지만 Yes 인 경우가 나오지는 않았다..

 

예를 들어 "( [ ] ( ) ) " 인 경우에는

 

내가 짠 알고리즘으로 진행할 시 " ( [ ] " 와 " ( ) ) " 를 비교하므로 당연히 No가 된다. 

 

하지만 원래 조건대로라면 Yes가 되어야 한다.

 

모르겠다.. 강의 실습코드를 보자 ㅠ

 

강의 실습코드

 

#include <bits/stdc++.h> 
using namespace std;
int main() {

    while (true) {
        string s;
        getline(cin, s);
        if (s == ".") break;
        stack<int> stk;
        bool check = true;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == ')') {
                if (stk.size() == 0 || stk.top() == '[') {
                    check = false;
                    break;                    
                }
                else {
                    stk.pop();
                }
            }
            if (s[i] == ']') {
                if (stk.size() == 0 || stk.top() == '(') {
                    check = false;
                    break;
                }
                else {
                    stk.pop();
                }
            }
            if (s[i] == '(') stk.push(s[i]);
            if (s[i] == '[') stk.push(s[i]);
        }
        if (check && stk.size() == 0)  cout << "yes\n";
        else cout << "no\n";
    }
    return 0;
}

 

이 짝짓기 문제에서는 "( ) " 또는 " [ ] " 가 무조건 한쌍으로 합쳐져야 하기 떄문에

 

괄호의 제일 안에 있는 ' ( ' 또는 ' [ ' 는 같은 유형의 괄호가 나와서 괄호를 닫아 줘야 규칙이 성립이 된다!

 

그래서 Stack 의 Top은 이전 글자에 해당하기 때문에 비교하여

 

만약 같은 괄호가 아닐 경우 "no" 를 출력하고

 

같은 괄호일 경우 "yes"를 출력하면 된다!!

 

세삼 느끼는 거지만 알고리즘 문제는 간단한 규칙만 생각해서 찾으면 되는데,

 

그게 제일 어려운 것 같다.....