[LeetCode] - 유효한 괄호

문제) 괄호로 된 입력값이 올바른지 판별하라 

https://leetcode.com/problems/valid-parentheses/

Valid Parentheses - LeetCode

 

▶ 입력 

[](){}

▶ 출력

true

---

풀이) 

 

이 문제는 전형적인 스택 문제로, 매우 쉬우면서 기본기를 점검할 수 있는 좋은 문제다. (, {, [ 는 스택에 푸시하고, ),},]를 만날 때 스택에서 pop한 결과가 매핑 테이블 결과와 매칭되는지 확인하면 된다. 

 

쉽게 예를 들어보자 

input : s = '[()]'

 

입력 s가 다음과 같을 때, '[' →'(' , ')' ,']' 순서로 반복문을 돈다. 

 

첫번째와 두번째 반복문에서 [ 와 ( 가 if char not in table 로 인해 stack에 append 된다. 

stack = [ '[' , '(' ]

 

세번째 반복에서 char = ' ) ' 이고 , table[ ' ) ' ]  = ' ( ' 이므로 stack.pop()을 하면 stack의 마지막 요소인 ' ( ' 가 삭제된다.

stack = [ '[' ]

 

네번째 반복에서 char = ' ] ' 이고 , table[ ' [ ' ]  = ' ] ' 이므로 stack.pop()을 하면 stack의 마지막 요소인 ' [ ' 가 삭제된다.

stack = []

 

 

이렇게 괄호로 된 입력값이 옳을 경우 stack이 비게 된다. 

 

 

 

전체풀이

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        
        stack = []
        table = { 
            ']' : '[', 
            '}' : '{',
            ')' : '('
        }

        for char in s :
            if char not in table :
                stack.append(char)
            elif not stack :
                return False
            elif stack.pop() != table[char] :
                return False
        return len(stack) == 0

---

 

유사한 문제 - 프로그래머스 : 올바른 괄호 

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

 

앞서 풀었던 리트코드보다는 간단한 문제이기 때문에 복습차원에서 풀면 쉽게 풀 수 있을 것이다. 

 

문제) 

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

 

풀이)

def solution(s):    
    stack = []
    for char in s :        
        if char =='(':
            stack.append(char)        
        elif not stack or stack.pop() != '(' :
            return False           
    return len(stack) == 0