C++로 표현식의 균형 잡힌 괄호 확인하기 – O(1) 공간, O(N²) 시간 복잡도

개념

'(', ')', '{', '}', '[', ']' 여섯 가지 문자로 이루어진 문자열 str이 주어졌을 때, 이 문자열의 괄호가 균형 잡혀 있는지(balanced) 판별하는 것이 목표입니다.

괄호가 균형 잡혀 있다고 판단되는 조건은 다음과 같습니다.

• 열린 괄호는 반드시 같은 종류의 괄호로 닫혀야 합니다.
• 열린 괄호는 올바른 순서에 따라 닫혀야 합니다.

입력 − str = "(()){}"

출력 − Yes

입력 − str = "))(([]["

출력 − No

풀이 방법

• 비교 대상이 되는 두 괄호의 위치를 추적하기 위해 두 개의 변수 a와 b를 사용합니다.
• 여는 괄호를 만나면 값이 증가하고 닫는 괄호를 만나면 값이 감소하는 카운트(count) 변수를 유지합니다.
• 여는 괄호를 만나면 b = a, a = a + 1, count = count + 1로 갱신합니다.
• 닫는 괄호를 만나면 count를 1 감소시킨 뒤, 현재 위치(i)와 이전 위치(j)의 괄호를 비교합니다.
  • a와 b 위치의 괄호가 서로 짝이 맞는다면, 문자열에서 해당 두 위치의 문자를 '#'으로 대체합니다. 이후 a는 계속 증가시키고 b는 계속 감소시키면서, '#'이 아닌 문자를 만나거나 b가 0 미만이 될 때까지 진행합니다.
  • a와 b 위치의 괄호가 짝이 맞지 않는다면 false를 반환합니다.
• 모든 문자를 처리한 후 count != 0이라면 false를 반환합니다.

예제 코드

// C++ implementation of the approach
#include <iostream>
using namespace std;
bool helperFunc(int& count1, string& s1, int& i1, int& j1, char tocom1){
    count1--;
    if (j1 > -1 && s1[j1] == tocom1) {
        s1[i1] = '#';
        s1[j1] = '#';
        while (j1 >= 0 && s1[j1] == '#')
            j1--;
        i1++;
        return 1;
    }
    else
        return 0;
}
bool isValid(string s1){
    if (s1.length() == 0)
        return true;
    else {
        int i1 = 0;
        int count1 = 0;
        int j1 = -1;
        bool result1;
        while (i1 < s1.length()) {
            switch (s1[i1]) {
                case '}':
                    result1 = helperFunc(count1, s1, i1, j1, '{');
                    if (result1 == 0) {
                        return false;
                    }
                break;
                case ')':
                    result1 = helperFunc(count1, s1, i1, j1, '(');
                    if (result1 == 0) {
                        return false;
                    }
                break;
                case ']':
                    result1 = helperFunc(count1, s1, i1, j1, '[');
                    if (result1 == 0) {
                        return false;
                    }
                break;
                default:
                    j1 = i1;
                    i1++;
                    count1++;
            }
        }
        if (count1 != 0)
            return false;
        return true;
    }
}
// Driver code
int main(){
    string str1 = "[[]][]()";
    if (isValid(str1))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

실행 결과

Yes