[BaekJoon 9012][⚪4] 괄호

❓ 문제

백준 9012 - “괄호”

🎯 난이도

Silver ⚪4

🧠 풀이

1. 내 풀이 (문자열)

- 알고리즘

• Data Structure, string

- 설명

문자열만을 사용해서 푸는 풀이이다.

사실상 이 문제의 본질은 stack을 사용하는 것이나, 그냥 문자열만으로 풀 수 있다. 문자열 내의 문자들을 순회하면서 괄호의 열림, 닫힘을 체크하는 방식으로 하면 간단하다. 그리고 그 코드는 깔끔하게 함수 하나로 뺐다.

반복문 하나를 돌리므로, 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <string>


using namespace std;

bool IsValid(const string& strInput);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iT{};
    cin >> iT;

    while(iT--)
    {
        string strInput{};
        cin >> strInput;

        cout << (IsValid(strInput) ? "YES" : "NO") << '\n';
    }

    return 0;
}

// 문자열이 VSP인지 확인하는 함수
bool IsValid(const string& strInput)
{
    int iBalance{};
    for(char chInput : strInput)
    {
        // 괄호의 열림, 닫힘에 따라 1을 더하거나 뺌
        iBalance = chInput == '(' ? iBalance + 1 : iBalance - 1;

        // 음수가 되면 바로 false 반환
        if(iBalance < 0)
        {
            return false;
        }
    }

    // 0이면 true, 아니면 false 반환
    return iBalance == 0;
}

---

2. 추가 풀이 (stack)

- 알고리즘

• Data Structure, stack

- 설명

stack을 사용하는 방식이다.

이 문제의 의도대로, 가장 정석인 stack을 이용한 풀이이다. 괄호의 종류에 따라 'stack'에 넣거나 빼거나 하면서 문자열을 검사하는 방식이다.

코드 자체는 위의 풀이와 크게 다르지 않지만, stack이라는 컨테이너를 하나 더 쓰는 것 뿐이다.

위와 똑같이 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <string>

#include <stack>


using namespace std;

bool IsValid(const string& strInput);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iT{};
    cin >> iT;

    while(iT--)
    {
        string strInput{};
        cin >> strInput;

        cout << (IsValid(strInput) ? "YES" : "NO") << '\n';
    }

    return 0;
}

// 문자열이 VSP인지 확인하는 함수
bool IsValid(const string& strInput)
{
    stack<char> stInput{};
    for(char chInput : strInput)
    {
        // 열린 괄호면 스택에 push
        if(chInput == '(')
        {
            stInput.push(chInput);
        }
        else
        {
            // 닫힌 괄호인데 스택 비어있으면 바로 false 반환
            if(stInput.empty())
            {
                return false;
            }

            // 닫힌 괄호이고 스택 비어있지 않으면 스택에서 pop
            stInput.pop();
        }
    }

    // 스택 비어있으면 true, 아니면 false 반환
    return stInput.empty();
}

---

💭 후기

사실상 정석은 두 번째 풀이인 stack을 이용하는 것이겠지만, 첫 번째 풀이가 더 간단하다. 게다가 stack 컨테이너를 쓰지 않기 때문에 헤더 파일 포함도 안해도 되고, 문자열 자체에서 모든 로직을 구현 가능하기 때문에 아주 미세하지만 성능도 첫 번째 풀이가 좀 더 좋다.