[실전 알고리즘] 0x08강 - 스택의 활용(수식의 괄호 쌍)

1. 수식의 괄호 쌍이란?

수식의 괄호 쌍 - 말 그대로 수식의 괄호 쌍을 의미하며 주어진 괄호 문자열이 올바른지 판단하는 문제이다.

---

2. 문제 해결을 위한 관찰

괄호 문자열이 올바른지 아닌지 판단하는 방법 중 가장 보편적인 방법은 바로 안쪽부터 짝맞추기를 해서 지워나가는 방법이다. 다 짝이 맞으면 올바른 괄호 쌍인거고 그렇지 않으면 올바르지 않은 괄호 쌍입니다.

+) ) 의 갯수가 ( 의 갯수를 넘지 않으면 된다.

 

그런데 괄호가 여러 종류일 때에는 여는 괄호의 갯수와 닫는 괄호의 갯수 만으로는 해결이 되지 않는다. 예를 들어 ({}), ({)}라는 두 괄호 문자열을 생각해보면 첫 번째는 올바르고 두 번째는 올바르지 않다. 그런데 둘 다 ) 의 갯수가 ( 을 넘은 적도 없고, } 의 갯수가 { 을 넘은 적도 없다.

 

대신 붙어있는 ( ) 혹은 { } 를 지우는 방법은 여전히 잘 동작한다. 이 방법은 배열로 구현할 경우 최대 N번 중간에 있는 원소의 삭제가 발생하기 때문에 O(N^2)이고, 연결 리스트로 구현할 경우 O(N)이다. 배열은 시간 복잡도가 안좋으니 거르고, 연결 리스트로 구현은 해볼만하니까 한 번 짜봐도 좋다. 그런데 스택을 이용하면 훨씬 더 간단하게 할 수 있다. 이 방법을 고안하려면 하나의 관찰이 추가로 더 필요하다.

 

그 관찰은 바로 "문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각해도 된다" 이다. 올바른 괄호 쌍일 경우 여는 괄호를 읽을 때 마다 저장하다가 닫는 괄호를 읽을 때 가장 최근에 들어온, 즉 가장 끝에 있는 여는 괄호와 짝을 이루게 해주고 pop을 하면 올바른 괄호 쌍인지 확인할 수 있습니다.

 

 

 

---

3. 문제 해결 방법

1. 여는 괄호가 나오면 스택에 추가

2. 닫는 괄호가 나왔을 경우,

 2-1 스택이 비어있으면 올바르지 않은 괄호 쌍

 2-2 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않는 괄호 쌍

 2-3 스택의 top이 짝이 맞는 괄호일 경우 pop

3. 모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호 쌍, 남아있지 않으면 올바른 괄호 쌍

 

이 과정을 잘 생각해보면 가장 최근의 것이 가장 먼저 나오게 되는 FILO인거고 스택 자료구조를 이용해서 구현을 할 수가 있다. 

 

---

4. 연습문제

BOJ 4949번: 균형잡힌 세상

4949번: 균형잡힌 세상

입력받는 부분에서 실수한 것을 유의하자. "."이면 입력이 종료되어야 하므로 "."을 delimeter로 받아오게 되면 무한 루프에 빠지게 된다. 따라서 getline으로 delimeter 없이 받아온 뒤에 "."이랑 같으면 break하는 식으로 해야 문자열을 끊고 입력을 종료하는 부분이 잘 처리된다.

 

또한 출력값이 2번씩 나오는 경우도 있었는데 이건 bool 값으로 flag를 만든 뒤에 최종적으로 flag에 따라 한 번씩만 출력해주면 잘 처리된다.

 

그리고 값이 다르게 나오는 것은 stack을 보다 큰 스코프에서 선언하여 제대로 초기화되지 않은 값을 썼기 때문이므로 이 점을 유의하면서 코드를 짜야 한다.

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // cout.tie(NULL);

    string s;
    while (true)
    {
        bool isCorrect = true;
        stack<char> stack;

        getline(cin, s);
        if (s == ".")
        {
            break;
        }
        for (auto c : s)
        {
            if (c == '(' || c == '[')
            {
                stack.push(c);
            }
            else if (c == ')')
            {
                if (stack.empty())
                {
                    isCorrect = false;
                    break;
                }
                else if (stack.top() != '(')
                {
                    isCorrect = false;
                    break;
                }
                stack.pop();
            }
            else if (c == ']')
            {
                if (stack.empty())
                {
                    isCorrect = false;
                    break;
                }
                else if (stack.top() != '[')
                {
                    isCorrect = false;
                    break;
                }
                stack.pop();
            }
        }
        if (!stack.empty())
        {
            isCorrect = false;
        }
        if (isCorrect){
            cout << "yes\n";
        }else{
            cout << "no\n";
        }
    }

    return 0;
}

조건문에서 일단 s.empty()를 먼저 확인하는 것을 볼 수 있는데, 만약 s.empty()가 true일 경우 뒤의 식을 확인하지 않고 바로 if문 안의 명령을 수행해서 스택이 비었는데 s.top()을 호출하는 일이 발생하지 않는다. 이런걸 Short-circuit evaluation이라고 한다.

 

BOJ 10799번: 쇠막대기

10799번: 쇠막대기

 

BOJ 2504번: 괄호의 값

2504번: 괄호의 값

---

참고자료

[실전 알고리즘] 0x08강 - 스택의 활용(수식의 괄호 쌍)

[실전 알고리즘] 0x08강 - 스택의 활용(수식의 괄호 쌍)