[강의 정리/Stack]

 

Stack 활용

1. LIFO 특성을 활용한 문제
2. DFS(깊이 우선 탐색)에 사용

 

예제

'(){}[]'를 포함하고 있는 문자열 s가 주어졌을 때, 괄호가 유효한지 아닌지 판별하라

 

제약조건

1 <= s.length <= 10의 4승

문자열 s는 '(){}[]'의 괄호들로만 구성되어 있다.

 

 

코드 설계 방법

s 문자열을 돌면서(반복문) 여는 괄호가 들어오면 stack에 push해주고, 닫는 괄호가 들어오면 짝이 맞다면 stack에 pop을 해줌. 짝이 맞지 않을 경우(유효하지 않은 괄호일 경우) return False. stack이 비어있다면 유효한 괄호만이 있다는 뜻이니까 return True를 해주면 됨.

 

stack에 push와 pop은 둘 다 O(1)의 시간복잡도를 가짐. 문자열을 반복하는 구간(n개의 문자열)은 O(n)의 시간복잡도를 가진다.

 

input: s = "{(([]))[]}" 라는 문자열의 괄호가 짝이 잘맞는지 확인해보자

 

def isValid(s):
    stack = []
    for p in s:
        if p == "(":
            stack.append(")")
        elif p == "{":
            stack.append("}")
        elif p == "[":
            stack.append("]")
        elif not stack or stack.pop() != p:
            return False
        return not stack


isValid("{(([]))[]}")