올바른 괄호

문제

첫 번째 해결방안

괄호의 개수가 같으면 올바르게 짝지어진 것이고, 개수가 다르다면 올바르지 않게 짝 지어진 것이라고 생각하여 각 괄호의 수를 세어 같으면 True를 반환하고 같지 않으면 False를 반환하는 방식으로 코드를 짰다.

input = "(())()"


def is_correct_parenthesis(string):
    left = 0
    right = 0
    for i in string:
        if i == '(':
            left += 1
        if i == ')':
            right += 1

    if left == right:
        return True
    else:
        return False


print(is_correct_parenthesis(input))

그러나 괄호의 개수가 같더라도 반대로 쓰여진 경우 예를 들어 (())인 경우가 아니라 ))((로 쓰여진 경우 개수는 같아도 올바르게 짝지어진 것이 아니므로 문제를 해결할 수 없다.

 

두 번째 해결방안

이번 주에 배운 스택자료구조를 사용하여 '('일 때 stack에 넣어주고, )이면 괄호가 닫힌 것이므로 pop해주어 stack의 길이가 0이면 True를 반환하고, 그렇지 않다면 False를 반환하도록 하였다.

input = "(())()"

def is_correct_parenthesis(string):
    stack = []
    for i in range(len(string)):
        if string[i] == '(':
            stack.append(i)
        elif string[i] == ')':
            if len(stack) == 0:
                return False
            stack.pop()

    if len(stack) == 0:
        return True
    else:
        False

print(is_correct_parenthesis(input))  # True 를 반환해야 합니다!

이 때 ')'가 들어오더라도 스택에 아무 값도 없어 닫을 수 없는 상태라면 올바르게 짝지어진 것이 아니므로 False를 반환한다.