프로그래밍 면접 문제 14: Check Balanced Parentheses

이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.

이전글 – 프로그래밍 면접 문제 13: Median of Integer Stream

열린 괄호와 닫힌 괄호로 이루어진 문자열이 주어지면, 해당 괄호가 균형을 이루는지 확인하는 문제입니다. 괄호의 유형은 다음과 같이 총 3가지 입니다: 소괄호(), 대괄호 [], 중괄호{}. 주어지는 문자열에는 이 괄호 외에 문자나 숫자, 공백 등 다른 문자가 포함되지 않는다고 가정합니다. 균형을 이루는 괄호는, 열린 괄호의 역순으로 닫힌 괄호가 나열되야 합니다. 예를 들어, ‘([])’는 균형을 이루지만, ‘([)]’는 균형을 이루지 않습니다.

이 문제는 또 다른 유형의 자료 구조 문제입니다. 자료 구조를 제대로 사용하면 이 문제는 매우 간단하게 해결할 수 있습니다. 문자열을 왼쪽에서 오른쪽으로 확인하면서 열린 괄호를 찾을 때마다 스택(Stack)에 넣는데, 이는 마지막으로 열린 괄호가 제일 먼저 닫혀야 하기 때문입니다. 그런 다음 닫힌 괄호를 찾으면 스택에서 마지막 요소를 빼낸 다음, 이렇게 얻은 열린 괄호와 방금 찾은 닫힌 괄호의 유형이 맞는지 확인합니다. 괄호의 유형이 일치하면 계속 진행하고, 일치하지 않으면 false를 반환합니다. 또는 스택이 비어있는 경우에도 닫힌 괄호와 짝을 이룰 열린 괄호가 없기 때문에 false를 리턴합니다. 마지막으로, 스택이 비어있는지 확인합니다. 스택이 비어있으면 true를 반환하고, 비어있지 않으면 괄호가 열린 상태로 닫히지 않았기 때문에 false를 반환합니다. 코드는 다음과 같습니다.

def isBalanced(expr):
    if len(expr)%2!=0:
        return False
    opening=set('([{')
    match=set([ ('(',')'), ('[',']'), ('{','}') ])
    stack=[]
    for char in expr:
        if char in opening:
            stack.append(char)
        else:
            if len(stack)==0:
                return False
            lastOpen=stack.pop()
            if (lastOpen, char) not in match:
                return False
    return len(stack)==0

이 문제는 스택의 올바른 사용법을 보여주는 간단하지만 면접에 자주 등장하는 문제입니다.

다음글 – 프로그래밍 면접 문제 15: First Non Repeated Character in String