(매일 BOJ) C++ 4949번 균형잡힌 세상

이번 문제는 실버 4 난이도의 4949번 균형잡힌 세상 문제이다.

1차 코드

처음에는 string 으로 전체 문장을 받은 후 괄호만 추출한 새로운 string을 만들고 여기서 () [] 을 지워나가는 방식으로 코드를 작성하였다.

문제점

🔸 괄호의 순서 & 중첩

예를 들어 입력이 아래와 같을 때: [(])

문자열 "[(])"에서 "[]"를 먼저 지우고 → "()"도 지우면 "[(])" → "()"
→ 결국 stk.size() == 0이 되어서 "yes"를 출력
❗ 하지만 실제로는 괄호가 잘못 닫힌 구조이므로 "no"가 되어야 한다.

따라서 이러한 중첩 문제를 해결하기 위해 stack 을 사용하여 다시 코드를 작성하였다.

# include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);
   
    while (1){ 
        string s;
        string stk;
        getline(cin,s,'.');
        if (s == ".") break;
        for (auto c : s){
            if (c == '(' || c == ')' || c == '[' || c == ']'){
                stk.push_back(c);
            }
        }
        while (stk.find("()") != string::npos) {
            stk.erase(stk.find("()"), 2);
        }
        while (stk.find("[]") != string::npos) {
            stk.erase(stk.find("[]"), 2);
        }
        if (stk.size() == 0) cout << "yes" << '\n';
        else cout << "no" << '\n';

    }
}

2차 코드

stack 을 사용하여 코드를 다시 작성하였다.

bool 변수를 사용하여 stack 이 비어있지 않은 경우에는 yes가 출력되지 않도록 판별하게 하였다.

# include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);
   
    while (1){ 
        string s;
        stack<char> stk;
        bool isValid = true;
        getline(cin,s);
        if (s == ".") break;
        for (auto c : s){
            if (c == '(' || c == '['){
                stk.push(c);
            }
            else if (c == ')'){
                if (stk.size() == 0 || stk.top() != '(') {
                cout << "no" << '\n';
                isValid = false;
                break;
                }
                stk.pop();
            }
            else if (c == ']'){
                if(stk.size() == 0 || stk.top() != '[') {
                    cout << "no" << '\n';
                    isValid = false;
                    break;
                }
                stk.pop();
            }

        }
        if (isValid && stk.empty()) cout << "yes" << '\n';
        else if (isValid == true) cout << "no" << '\n';

    }
}

 

처음 생각보다 힘들게 풀었던 문제였던 것 같다

앞으로는 문제를 제대로 읽고 풀어야겠다