[BaekJoon 4949][⚪4] 균형잡힌 세상

❓ 문제

백준 4949 - “균형잡힌 세상”

🎯 난이도

Silver ⚪4

🧠 풀이

1. 내 풀이 (stack)

- 알고리즘

• Data Structure, stack

- 설명

stack 컨테이너를 사용해 푸는 방식이다.

전형적인 괄호 순서 문제로, 이런 유형의 대부분의 문제는 stack을 사용해서 풀면 쉽다. stack에 들어오는 괄호 중에 열린 괄호를 넣어주고, 닫힌 괄호가 들어오면 stack의 맨 위의 괄호와 비교하는 것이다.

stack의 값과 비교하며 push, pop하는 과정이 겹치는 부분이 많아서 람다 함수를 만들어 보았다. 따로 함수로 빼도 되겠지만, 코드의 길이가 길지 않고 매개변수를 넘기는게 편하므로 '람다'로 처리했다.

테스트 케이스의 수가 N인 경우에 시간 복잡도가 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <stack>

#include <string>


using namespace std;

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

    string strInput{};
    while(getline(cin, strInput))
    {
        // "."만 들어오면 입력 종료
        if(strInput == ".")
        {
            break;
        }

        stack<char> stInput{};
        bool bBalanced{ true };

        // 스택의 맨 위 값과 비교하는 람다 함수
        auto IsMatch = [&](char chTop) -> bool
        {
            if(!stInput.empty() && stInput.top() == chTop)
            {
                stInput.pop();
                return true;
            }
            
            return false;
        };

        for(char chInput : strInput)
        {
            // 열린 괄호면 push
            if(chInput == '(' || chInput == '[')
            {
                stInput.push(chInput);
            }
            // 닫힌 괄호면 IsMatch 람다 함수로 비교
            else if(chInput == ')')
            {
                if(!IsMatch('('))
                {
                    bBalanced = false;
                    break;
                }
            }
            else if(chInput == ']')
            {
                if(!IsMatch('['))
                {
                    bBalanced = false;
                    break;
                }
            }
        }

        // 스택 비어있지 않으면 bBalanced = false;
        if(!stInput.empty())
        {
            bBalanced = false;
        }

        cout << (bBalanced ? "yes" : "no") << '\n';
    }

    return 0;
}

---

💭 후기

전형적인 괄호 문제이다. 특별한 점도, 어려운 점도 없었다.

주목할 부분이라면 나의 풀이에서 람다를 통해 공통 부분을 따로 빼준 것 정도이다. 이렇게 하면 람다 또한 함수이기 때문에 호출 비용이 증가 할 수 있지만, 코드가 길지 않아서 아마 인라인화될 가능성이 높아서 쓰지 않는 것과 성능 차이도 거의 미미할 것이라 보인다. 하지만 만약 'function'을 써서 한 번 더 감싸준다면 확실히 비용이 늘어날 가능성이 높으므로 웬만하면 '람다'를 써주도록 하자!