LIFO 예제(Stack 활용) Valid parentheses

Valid parentheses(괄호 유효성 검사)

1. 문제이해하기. 

즉 괄호가 잘 열고 닫혔는지를 판단해야한다

제약조건

10^4 까지로 되어있으니까 n^2의 시간복잡도는 제외해야함(예를 들면 2중 반복문 같은거)

2. 접근방법

단순화 해보기

() : 유효

)(): 비유효

)( : 비유효

• 여는 괄호가 있으면 닫는 괄호가 있어야한다. 괄호의 개수는 짝수여야한다
• 항상 처음은 여는 괄호여야한다

확장

그러면 이걸 어떻게 판별하냐?

여는괄호 : +1

닫는 괄호: -1

예시 : () (())

( : 1

) : 0

---

( : 1

( : 2

) : 1

) : 0

즉 짝이 맞으면 값이 0 으로 끝난다

만약 0 이상으로 나오면 여는 괄호가 더 많았을 것으로 invaild

만약에 여는 괄호가 먼저 시작을 안하고 닫는 괄호가 먼저 시작했을 경우엔 어떻게 판별하나

예시

)(

) : -1

( : 0

0으로 끝나긴 하지만 음수가 들어가버릴 것 invaild

예외상황 확인

예시 : ( ]

( : 1

] : 0

...???

이렇게 되면 안됨!!! 괄호의 종류가 다를 경우를 생각해야함

즉 괄호마다 각각 따로 카운팅을 해줘야한다

 

예시2 : ( [ )

안에 있는 괄호가 닫히기 전에 바깥 괄호를 닫으면 invaild

 

=> 즉 (({{[ 이렇게 되어있을 때 마지막에 들어온 [ 라는 괄호를 먼저 해결해줘야한다(LIFO) => Stack 자료구조를 사용하면 된다

 

위 처럼 짝이 맞으면(괄호의 계산이 0이라면) pop을 해서 가장 안쪽의 괄호부터 빼주면 된다

3. 코드 설계

s = "임의의 괄호들"

for i in s:
	if 'c { ]': # 대중소 괄호 중 여는 것들이 들어오면
    	stack.push()
    if ' )}]':
    	짝이 맞을때 : stack.pop()
        짝이 맞지않을 때 : return False

반복문이 끝나고 나서
stack.isEmpty() => True
		        => Flase

시간 복잡도

push(), pop()은 시간복잡도 O(1) => 반복문 안의 시간복잡도는 O(1)

반복문은 s라는 문자열의 길이가 n일때 n번 반복하기 때문에 O(n)

즉 전체 코드는 O(n)의 시간복잡도로 해결 가능함

포인트

포인트는  [ 이 괄호와 ] 이 괄호가 짝이 맞는지 확인하는 방법은 숫자로도 가능하지만 생각을 살짝 전환 해보면

s를 순회하다가 [ 이 괄호를 만났을때 스택에 ] 이걸 append 해주면 나중에 ] 닫는 대괄호가 나왔을때 그냥 같은지만 검사해주면 된다

4. 코드 구현

class Solution:
    def isValid(self, s: str) -> bool:
        # 괄호를 넣을 스택을 하나 만든다
        stack = []
        
        # 괄호 요소들을 순회
        for p in s:
            # 여는 괄호를 만나면 닫는 괄호를 스택에 넣는다
            # 그래야 제대로 닫힌건지 확인이 가능하다
            if p == "(":
                stack.append(")")
            elif p == "{":
                stack.append("}")
            elif p == "[":
                stack.append("]")
            # 스택이 비엇다면 괄호가 전부 닫힌것으로 반복문을 빠져나오고
            # 남아 있으나 검사할 요소랑 같다면 마지막에 있는 괄호를 제거해준다
            elif stack or stack[-1] == p:
                stack.pop()
            # 모두 아니라면 괄호가 잘못 들어간것
            else:
                return False
        # 반복문을 빠져나오면 true 반환
        # 파이썬에서 빈 리스트는 false 요소가 하나라도 있다면 true이기 때문에 이걸 not으로 바꿔줌
        # 즉 반대로 비어있다면 true, 요소가 하나라도 있다면 false 반환
        return not stack