[Hackerrank] Balanced Brackets

문제: 균형 잡힌 괄호 (Balanced Brackets)

괄호는 다음과 같은 문자 중 하나로 정의됩니다: {, }, (, ), [, ].

열린 괄호가 닫힌 괄호와 쌍을 이루는 경우를 짝이 맞는 괄호라고 정의합니다. 예를 들어, {}, [], ()는 모두 짝이 맞는 괄호입니다.

괄호 쌍이 균형을 이루지 못한 경우는 괄호 안에 포함된 괄호가 짝이 맞지 않는 경우를 말합니다. 예를 들어, {{[}}는 균형을 이루지 못한 예입니다. 이 경우, 다음과 같은 이유로 균형이 맞지 않습니다:

• 중괄호({}) 쌍 안에 포함된 대괄호([])가 짝이 맞지 않습니다.
• 대괄호는 한 쌍을 이루지 못한 열린 괄호 [로 끝납니다.

이러한 규칙에 따라, 괄호가 균형을 이루는 경우는 다음 조건을 만족해야 합니다:

1. 모든 괄호가 짝이 맞아야 합니다.
2. 짝을 이루는 괄호 안에 포함된 괄호들도 모두 균형을 이루어야 합니다.

문자열 s에 대해, 괄호가 균형을 이루면 YES를 반환하고, 그렇지 않으면 NO를 반환하세요.

---

함수 설명:

isBalanced 함수를 작성하세요.
이 함수는 다음의 매개변수를 받습니다:

• string s: 괄호로 이루어진 문자열

반환값:

• 균형을 이루는 경우: 문자열 "YES"
• 균형을 이루지 못하는 경우: 문자열 "NO"

이 문제는 모든 문자가 짝이 맞으면 YES를 아니라면 NO를 반환해야한다. 그래서 기본적인 아이디어는 스택을 선언하고 문자열의 맨 앞에서부터 탐색한다. 만약 여는 괄호('{', '[', '(')가 나온다면 스택에 push한다. 만약 닫는 괄호가 나오면, 스택에서 가장 최근에 추가된 값을 꺼내서 (pop) 짝이 맞는지 확인한다. 만약 짝이 맞지 않는다면 NO를 반환한다. 이런 식으로 문자열을 지우고 마지막에 스택이 비어있다면 모든 문자가 짝을 이룬것이니 YES를 반환하고, 문자가 하나라도 남아있다면 모든 문자열들이 짝을 이루지 못한 것이므로 NO를 반환한다.

코드는 다음과 같다.

from collections import deque
def isBalanced(s):
    q = deque()
    for i in range(len(s)):
        if s[i] == "{" or s[i] == "(" or s[i] == "[":
            q.append(s[i])
        elif s[i] == "}" and len(q) != 0:
            x = q.pop()
            if x != "{":
                return "NO"
        elif s[i] == ")" and len(q) != 0:
            x = q.pop()
            if x != "(":
                return "NO"
        elif s[i] == "]" and len(q) != 0:
            x = q.pop()
            if x != "[":
                return "NO" 
        else:
            return "NO"
    if q:
        return "NO"
    return "YES"