[Stack] 프로그래머스 “대중소 괄호 짝 맞추기” Python 풀이

문제 설명

• 여섯 가지 괄호 '(', ')', '{', '}', '[', ']'로 이루어진 문자열이 바르게 닫힌 문자열인지 알아보려 합니다.

• 바르게 닫힌 문자열이라는 것은

• '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로,

• '[' 문자로 열렸으면 반드시 짝지어서 ']' 문자로,

• '{' 문자로 열렸으면 반드시 짝지어서 '}' 문자로 닫히는 문자열입니다.

• 또한, 괄호 쌍 안에는 다른 괄호 쌍이 들어갈 수 있습니다.

• 예제 입력 및 출력은 아래와 같습니다.

    “{{}}” 또는 “({})[]” 는 바르게 닫힌 괄호입니다.
    “[)”, “]()[”, “([())]”는 바르게 닫히지 않은 괄호입니다.

• 문자열 s가 주어졌을 때,

• 문자열 s가 바르게 닫힌 괄호이면 true를,

• 그렇지 않으면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

• 문자열 s는 (, ), {, }, [, ] 로만 이루어졌습니다.
• 문자열 s의 길이는 1 이상 40 이하입니다.

풀이

• 기본적인 스택 문제입니다.
• 우선, { ‘닫는 괄호’ : ‘여는 괄호’ } 형식으로 모든 괄호를 사전으로 생성합니다.
• 이후, stack을 생성한 뒤,
• 문자열 s를 처음부터 훑으면서 열린 괄호라면 stack에 push하고
• 닫힌 괄호라면 stack에서 pop한 top과 비교합니다.
  • 닫힌 괄호와 top이 짝이 맞지 않는다면 False
  • 닫힌 괄호가 등장했지만, 스택에 열린 괄호가 없을 경우 False
• 세부 풀이는 아래 코드에 설명되어있습니다.

코드

def solution(s):

    # {닫는괄호 : 여는괄호} 형식으로 사전 생성
    dic = {')' : '(', ']' : '[', '}': '{'}

    # 스택 생성
    stack = []

    # 문자 검색
    for char in s:

        # 문자가 여는 괄호라면
        if (char in '({['):
            # 스택에 삽입
            stack.append(char)

        # 문자가 닫는 괄호라면
        else:

            # 스택에 열린 괄호가 남아있다면
            if (stack):

                # 스택 top의 열린 괄호
                top = stack.pop()

                # 해당 닫힌 괄호와 스택 top의 열린 괄호가 짝이 맞지 않는다면
                if (dic[char] != top):
                    return False

            # 스택이 비어있다면
            else:
                return False

    return True


print(solution("{{}}"))
print(solution("({})[]"))
print(solution("[)"))
print(solution("]()["))
print(solution("([())]"))