프로그래머스 - 대중소 괄호 짝 맞추기

1. 문제

출처 : 프로그래머스

2. 소스코드

def solution(s):     stack = []     match = {'(':')', '{':'}', '[':']' }     for x in s:         # 여는 괄호         if x in match:             stack.append(x)         # 닫는 괄호         else:             if not stack: return False             if match[stack.pop()] != x:                 return False         return not stack

 

3. 고찰

1) 알고리즘

여는 괄호이면 스택에 push

닫는 괄호이면 (1) 스택이 비어있는지 검사

                   (2) 스택의 top과 매치하는 괄호인지 검사한다.

문자열 s의 모든 괄호에 대해 위 과정을 반복한 후 스택이 비어있으면 True를 리턴한다.

 

2) 시간복잡도

문자열 s의 모든 괄호에 대해 for loop -> O(N)

    리스트에 append -> O(1)

    닫는 괄호이면 pop -> O(1)

따라서 위 코드의 시간복잡도는 O(N)이다.