Codility - Brackets (Stacks and Queues) [Python]

 

 

 문제

 

app.codility.com/programmers/lessons/7-stacks_and_queues/brackets/

Brackets coding task - Learn to Code - Codility

 

 

 

 

 

 

 

 문제 상황

 

- 전형적인 Stack 문제로 올바른 괄호 찾기 문제이다.

 

 

 

 

 

 

 해결 전략

 

- 검색 속도가 빠른 dict를 이용해 짝을 구성하여 open bracket일 경우 stack에 저장, close bracket의 경우는 open bracket에서 pop하여 비교해서 같으면 제거, 다르면 잘못된 bracket이므로 return 0을 한다.

 

 

 

 

 

 

 코드

 

def solution(S):
    brackets = {"(":")", "{":"}","[":"]"}
    stack = []
    for char in S:
        if brackets.get(char, False): # 여는 괄호이면
            stack.append(char)
        else: # 닫는 괄호이면
            if not stack or brackets[stack.pop()] != char: return 0 # stack 마지막의 괄호와 매칭이 안되면
    if stack: return 0 # stack에 남은 요소가 있으면    
    else: return 1 # stack이 비어있으면

 

 

 

 

 

 

 

 

 해설

 

- 괄호의 짝은 반드시 가장 가까이에 닫히는 괄호가 존재해야하므로 후입선출(LIFO)의 구조 Stack을 활용한다.

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- dict에서 요소를 찾을 때에는 O(1)로 처리하기위해 Hash를 사용하고, get 함수를 이용해 예외상황을 처리했지만 Stack에서 pop할 때는 예외를 생각하지 못했다. 그래서 런타임 에러가 발생했다. 

 

- Overflow나 Underflow 상황을 고려할 필요가 있다. 항상 함수를 쓸 때 서둘지 말고 머리속으로 상황을 그려야한다.