Written by JS970
on February 9, 2023

4949 - 균형잡힌 세상

난이도: 실버 4
날짜: 2023년 2월 9일
상태: Correct/Retry
추가 검토 여부: Yes
알고리즘 : stack

solution

입력받은 문자열에 대해서 string헤더의 substr함수를 사용하여 재귀적으로 검사하였다.
소괄호와 대괄호가 알맞게 열리고 닫힌 경우에 대해 그 안의 모든 문자열을 재귀함수의 입력으로 넣었다.
결과적으로 정답이었으나 상당히 많은 시행착오가 있었고 적지 않은 시간을 소모했다.
stack을 사용하여 훨씬 간단한 풀이가 가능하다.
- 괄호가 열리고 닫히는 과정을 stack을 통해 안정적으로 구현 가능하다.

code

#include <iostream>
#include <string>
using namespace std;

bool balance(string msg)
{
    int depth = 0;
    int start = -1, end = -1;
    bool ret = true;
    bool subbalance = true;
    string sub;

    for(int i = 0; i < msg.size(); i++)
    {
        if(msg[i] == '(')
        {
            if(start == -1)
                start = i;
            depth++;
        }
        if(msg[i] == '[')
        {
            if(start == -1)
                start = i;
            depth++;
        }
        if(msg[i] == ')')
        {
            if(msg[start] == '(' && depth == 1)
                end = i;
            depth--;
        }
        if(msg[i] == ']')
        {
            if(msg[start] == '[' && depth == 1)
                end = i;
            depth--;
        }
        if(start != -1 && end != -1)
        {
            sub = msg.substr(start+1, end-start-1);
            subbalance = balance(sub);
            start = -1, end = -1;
        }
        if(depth < 0 || !subbalance)
        {
            ret = false;
            break;
        }
    }

    if(depth != 0) ret = false;
    if(start != -1 && end == -1) ret = false;
    return ret;
}

int main()
{
    string message;
    while(1)
    {
        getline(cin, message);
        if(message == ".") break;
        if(balance(message)) cout << "yes" << endl;
        else cout << "no" << endl;
    }

    return 0;
}

stack을 사용한 풀이

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

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

ref

4949번: 균형잡힌 세상

stack 사용한 풀이 로그인

Top