[Top Interview Questions] 20. Valid Parentheses

정답)

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        closeToOpen = {")" : "(", "]" : "[", "}" : "{"}

        for parenthesis in s:
            
            # 만약 열린 괄호라면 스택에 추가
            if parenthesis not in closeToOpen:
            	stack.append(parenthesis)
            
            # 만약 닫힌 괄호라면    
            else:
            	# 만약 스택이 비어있지 않고 
                # 스택의 top이 닫힌 괄호와 상응하는 열린 괄호라면
                if stack and stack[-1] == closeToOpen[parenthesis]:
                
                    # 스택에서 제거
                    stack.pop()
                else:
                    return False
            
                
        
        # 스택이 비어있다면 True, 스택에 괄호가 남아있다면 False
        return True if not stack else False

풀이출처: NeetCode (오늘도 유튜브에 일용할 양질의 풀이 과정을 올려주시는 NeetCode님께 기도를 올립시다. 코멘.)

문제)

문제출처

 

주어진 문자열 s에는 괄호 '(', ')', '[', ']', '{', '}' 문자들로 이루어져 있습니다. 이 문자열 s가 유효한지 알아내시오.

 

s가 유효한 기준:

• 열린 괄호는 무조건 올바른 순서로 같은 종류의 닫힌 괄호로 끝나야 한다.

예시 1)

s = "()"

output = True

 

예시 2)

s = "()[]{}"

output = True

 

예시 3)

s = "(]"

output = False

풀이)

1) 풀이 기본 원리

NeetCode가 알려준 기본 원리는 이렇습니다.

 

주어진 문자열 s를 선형검색하며 열린 괄호가 발견되면 스택에 집어넣습니다. 그러다 s에서 닫힌 괄호가 발견되면 스택의 top (맨 위)을 확인합니다. s에서 발견된 닫힌 괄호와 스택의 top의 열린 괄호가 같은 종류라면 스택의 탑(top)을 제거합니다. 

 

위와 같은 방식으로 추가, 발견, 제거를 반복하며 선형검색이 끝나면 스택을 확인합니다. 만약 스택이 비어있다면 s에는 알맞은 개수의 괄호가 짝을 이루고 있었다는 뜻으로 True를 리턴합니다. 하지만 스택에 괄호가 남아있다면 짝이 맞지 않다는 뜻이기 때문에 False를 리턴합니다.

 

결국 스택이 비었냐 안 비었냐에 따라 결괏값을 리턴합니다.

2) Stack와 Dictionary

어떤 괄호가 어떤 괄호와 상응하는지 확인하기 위해서 딕셔너리를 사용했습니다. 딕셔너리의 key와 value를 사용하여 '('와 ')'를 짝으로 맞춰줄 수 있기 때문입니다. 

 

여기까진 저 혼자서 생각해 냈지만 그 이후로 어떤 식으로 괄호들을 비교하고 어떻게 결괏값을 리턴할지 모르겠더라고요. NeetCode는 Stack을 활용했습니다.

 

괄호가 올바른 순서로 되어있다는 것을 확인하기에 스택이 알맞은 이유는 부분적으로 봤을 때 괄호들은 바로 옆에 붙어있어야 되기 때문입니다. 

 

"( { [ ] } )"

 

위 괄호들은 올바른 순서로 정렬되어 있습니다. 

 

부분적으로 봤을 때 '[' 와 ']'는 바로 옆에 붙어있습니다. 이렇게 올바르게 정렬된 괄호를 제외합니다.

다음 괄호를 보시죠.

 

"( { [ ] } )"

 

또 부분적으로 봤을 때 '{' 와 '}'는 바로 옆에 붙어있습니다. "{ }"를 제외하면 "( )" 또한 마찬가지입니다.

 

이런 식으로 NeetCode는 괄호들이 서로서로 붙어있다는 성질을 이용해 스택을 사용할 생각을 한 거죠. 릿코드를 잘 풀기 위해서는 이런 분석하는 능력과 응용이 굉장히 중요한 것 같습니다.

3) 스택과 딕셔너리 정의하기

빈 스택은 리스트를 활용하여 정의해 줍니다.

 

딕셔너리는 닫힌 괄호가 key, 열린 괄호가 value로 되게끔 설정해 줍니다.

def isValid(self, s: str) -> bool:
        stack = []
        closeToOpen = {")" : "(", "]" : "[", "}" : "{"}

4) 열린 괄호가 발견되면

s문자열의 괄호들을 선형 검색하며 딕셔너리를 활용해 괄호가 열린 괄호인지 확인합니다. closeToOpen의 key가 닫힌 괄호들이므로 만약 주목하고 있는 괄호가 closeToOpen의 key에 존재하지 않는다면 현재 괄호는 열린 괄호겠죠? 그럼 스택의 탑에 저장해 줍니다. 

 

이렇게 스택의 탑 (리스트로 봤을 땐 맨 뒤겠죠?)에 원소를 추가하는 것을 push라고 합니다. 리스트에서 비슷한 기능을 해주는 메서드는 append() 입니다.

def isValid(self, s: str) -> bool:
        stack = []
        closeToOpen = {")" : "(", "]" : "[", "}" : "{"}

        for parenthesis in s:
            if parenthesis not in closeToOpen:
            	stack.append(parenthesis)

5) 닫힌 괄호가 발견되면

만약 주목하고 있는 괄호가 closeToOpen의 key에 발견되면 현재 괄호는 닫힌 괄호입니다. 기본원리에서 설명했듯이 괄호들이 올바른 순서대로 정렬되어 있다는 것은 부분적으로 바로 옆에 붙어있다는 뜻입니다.

 

그러므로 닫힌 괄호가 발견되면 바로 이전의 괄호가 상응하는 열린 괄호인지 확인해야 합니다. 이 2개의 괄호들이 상응하는지 확인하기 위해선 2가지 조건이 필요합니다:

 

1. 스택이 비어있지 않다.
2. 스택의 탑의 괄호가 현재 괄호와 상응하는 열린 괄호이다.

스택이 비었는지 확인하는 이유는 간단합니다.

 

만약 s = ')' 일 경우, s의 괄호는 닫힌 괄호입니다. 하지만 이전에 열린 괄호가 없었기 때문에 스택은 비어있는 상태이죠. 비어있는 스택에서 열린 괄호를 꺼내올 수는 없기 때문에 먼저 스택이 비어있는지 확인해야 합니다.

 

그리고 만약 스택이 비어있지 않다면 스택의 탑(즉, stack[-1])의 열린 괄호가 닫힌 괄호와 상응하는지 딕셔너리를 활용해 확인하면 되겠죠.

 

위 2조건에 부합한다면 스택에서 그 열린 괄호를 빼줍니다. 열린 괄호를 빼준다는 건

 

"( { [ ] } )"

에서

"( { [ ] } )"

 

가 된다는 뜻이고 다음 닫힌 괄호에 한해 부분적으로 붙어있는지 확인할 수 있겠죠.

 

스택의 탑을 빼주는 행위를 pop이라고 부릅니다. 리스트에서도 똑같이 pop() 메서드를 사용하면 맨 뒤 원소 (즉, -1번째 원소)가 리스트에서 제거됩니다.

 

def isValid(self, s: str) -> bool:
        stack = []
        closeToOpen = {")" : "(", "]" : "[", "}" : "{"}

        for parenthesis in s:
            if parenthesis not in closeToOpen:
            	stack.append(parenthesis)
 
            else:
                if stack and stack[-1] == closeToOpen[parenthesis]:
                    stack.pop()
                else:
                    return False

6) 스택이 비었나 안 비었나

주어진 문자열 s를 전부 선형검색했다면 이제 스택을 확인합시다.

 

스택이 비었다는 건 무슨 뜻일까요? 스택이 비었다는 건

 

"( { [ ] } )"

에서

"( { [ ] } )"

 

가 됐다는 뜻이죠. 즉 s는 괄호들이 올바른 순서로 정렬되어 있다는 뜻입니다.

 

스택이 안 비었다는 건 무슨 뜻일까요? 스택이 안 비었다는 건

 

"( ( )"

에서

"( ( )"

 

가 됐다는 뜻이죠. 스택에 '('가 남아있습니다. 그러므로 s는 괄호들이 제대로 정렬 안되었죠.

 

def isValid(self, s: str) -> bool:
        stack = []
        closeToOpen = {")" : "(", "]" : "[", "}" : "{"}

        for parenthesis in s:
            if parenthesis not in closeToOpen:
            	stack.append(parenthesis)
                
            else:
                if stack and stack[-1] == closeToOpen[parenthesis]:
                    stack.pop()
                else:
                    return False

        return True if not stack else False

예시) 

s = "{ ( ) }"

 

stack = [ ]

closeToOpen = { ")" : "(", "]" : "[", "}" : "{" }

 

( parenthesis = '{' )    # 열린 괄호 임으로 스택에 추가

stack = ['{']

 

( parenthesis = '( )    # 열린 괄호 임으로 스택에 추가

stack = ['{', '(']

 

( parenthesis = ')' )    # 닫힌 괄호 임으로 스택의 탑과 상응하는지 비교

'(' == closeToOpen( ')' )

stack = ['{']    # 상응함으로 스택에서 탑 제거

 

( parenthesis = '}' )    # 닫힌 괄호 임으로 스택의 탑과 상응하는지 비교

'{' == closeToOpen( '}' )

stack = [ ]    # 상응함으로 스택에서 탑 제거

 

return True

 

오늘 문제는 edge case가 너무 많아서 글로 하나하나 설명한다고 길어졌네요. 끝까지 읽어주셔서 감사합니다 (_ _)

제가 미디움이나 어려움 단계로 가면 좀 더 간결하게 설명해 보겠습니다. 아직은 코린이라 동료 코린이분들도 쉽게 이해할 수 있도록 주절주절 설명 중입니다 ㅎㅎ...

 

오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)