[SW Expert Academy] 괄호 짝짓기

괄호 짝짓기

SW Exeprt Academy의 문제들은 무단복제가 금지되어있기 때문에 링크로 대체합니다.

어떻게 풀까?

대표적인 스택 활용 문제입니다. 열린 괄호의 경우에는 모두 스택에 저장합니다.

그리고, 닫힌 괄호가 나타나면 스택의 맨 위의 괄호와 비교합니다.

만약, 스택의 맨 위의 열린 괄호와 현재 나타난 닫힌 괄호가 매칭이 되지 않는다면 제대로 맞지 않는 괄호겠죠!

또한, 마지막에 스택 사이즈도 확인해야 합니다.

스택 사이즈가 0이 아니라면, 열린 괄호가 많이 남아있다는 것이겠죠! 이 상황도 괄호의 짝이 맞지 않는 경우입니다.

간단한 예시 문제 2개를 풀어보겠습니다.

열린 중괄호이기 때문에 스택에 넣습니다.

마찬가지로 열린 대괄호이기 때문에 스택에 넣습니다.

마찬가지로 열린 소괄호이기 때문에 스택에 넣습니다.

열린 중괄호입니다. 스택의 맨 위의 괄호와 짝이 맞는지 비교합니다.

짝이 맞지 않기 때문에 유효하지 않습니다.

2번 예제입니다.

열린 대괄호를 스택에 넣습니다.

열린 대괄호를 스택에 넣습니다.

닫힌 대괄호이기 때문에 스택의 맨 위의 괄호와 짝이 맞는지 비교합니다.

짝이 맞기 때문에 계속 진행합니다.

열린 소괄호이기 때문에 스택에 넣습니다.

닫힌 소괄호입니다. 스택과 짝이 맞습니다.

하지만, 스택이 비어있지 않기 때문에 괄호의 짝이 맞지 않다는 것을 알 수 있습니다!

코드

#pragma once
#include<cstdio>
 
char stack[1000];
int top;
 
//캐릭터는 0~255 값이기 때문에 256 크기의 배열을 선언하면 모든 문자에 대해서 변환을 수행할 수 있습니다.
char str[1000], check[256];
 
int main()
{
    //닫힘괄호는 열린괄호와 비교를 해야합니다. 이를 배열에 저장해둡니다.
    check['>'] = '<';
    check[')'] = '(';
    check[']'] = '[';
    check['}'] = '{';
 
    for (int tc = 1; tc <= 10; tc++)
    {
        int len;
        scanf("%d\n%s\n", &len, str);
        top = 0;
        bool valid = true;
 
        for (int i = 0; i < len && valid; i++)
        {
            switch (str[i])
            {
            case '(':
            case'{':
            case'[':
            case'<':
                stack[top++]= str[i];
                break;
            case')':
            case'}':
            case']':
            case'>':
 
                //empty
                if (top == 0)
                {
                    valid = false;
                    break;
                }
 
                char t = stack[--top];
 
                //짝이 맞지 않는다.
                if (t != check[str[i]]) valid = false;
                break;
            }
        }
        //스택이 비어있지 않다. (열린 괄호가 많다.)
        valid = top == 0;
        printf("#%d %d\n", tc, valid);
    }
    return 0;
}

여담

스택에 넣고 빼는 것은 O(1)입니다. 문자열의 길이만큼 반복하기 때문에, 시간 복잡도는 O(n)이라는 것을 알 수 있습니다.