[자료구조] [python] Balanced Brackets (stack)

Hackerrank의 Data structures 관한 문제 중에서 Medium에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. 

www.hackerrank.com/challenges/balanced-brackets/problem

Balanced Brackets | HackerRank

 

 

•     Stack의 개념과 가장 맞닿아 있는 문제이다. 빈출되었던 문제이기도 하다. 문제를 풀이하는데 있어서 어려웠던 점은 다음과 같다. 괄호의 순서가 '균형되어'(Balanced) 있다면,  '{[()]}' 완전히 양쪽의 대괄호가 균형된 예시만을 처리하는 것인가? 아니면, 어느 대괄호를 열고 닫는 순서와 관계 없이, 여는 괄호로 시작했으면, 닫는 괄호가 이후에 어디에 위치하든 상관이 없는것인가? 문제의 예시를 보면, { [ ( 가장 최근의 열었던 괄호의 종류로 괄호를 닫았는지 판별하는 알고리즘을 만들어야 한다. 

 

•     딕셔너리 자료구조는 key값을 알고 있다면, value값을 찾는데 O(1) 탐색시간이 걸린다. 딕셔너리 형태로 괄호의 여닫는 짝을 매칭하였다. 리스트로 stack을 만들어, 만약 입력 인자 중에서 닫는 괄호(']',')','}')가 나타난다면, stack의 마지막 요소를 빼서 제대로 매칭되었는지 확인하였다. 문제를 풀면서 애를 먹었던 지점 중에 하나는 if문에 pop()함수를 써서 if string != stack.pop(): 괄호가 여닫는 게 제대로 이뤄지고 있는지 확인하였으나, 몇몇의 테스트 케이스에서 런타임 오류가 발생하였다. 아직도 정확한 이유를 모르겠으나, 실전상황에서는 새로운 변수를 추가해서 right_thing = stack.pop(), 작은 문제에서 많은 시간을 소비하지 않도록 노력해야겠다.

def isBalanced(s):
   
    sign = {'}':'{', ']':'[', ')':'('}
    stack = []
    
    for temp in s:
        
        if temp in ['{', '[', '(']:
            stack.append(temp)
        else:
            if not stack:
                return 'NO'
            right_thing = stack.pop()
            if sign[temp] != right_thing:
                return 'NO'
    
    
    if stack:
        return 'NO'
    else:
        return 'YES'
        
    # lastly, check that stack is empty or not  
    if len(stack) != 0:
        return 'NO'
              
    return 'YES'