20. Valid Parentheses

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

Valid Parentheses - LeetCode

이번 문제는 굉장히 유명한 문제죠.

 

괄호의 짝을 구하는 문제입니다 !

 

보통 자료구조 stack을 공부할 때 같이 나오는 문제로서, 쉽게 해결할 수 있는 문제입니다.

 

심심풀이 땅콩과 같은 문제랄까?

 

이렇게 크게 보니 귀엽네요

stack을 만들어서 여는 괄호가 들어오면 stack에 집어넣습니다.

 

닫는 괄호가 나오면 어떻게 할까요? stack의 젤 위에 값을 꺼내어 그 괄호의 짝을 보도록 합시다. 만약 그 짝이 다르면 순서가 뒤죽박죽인거니 바로 False를 return 하면 됩니다.

 

그리고 문자열을 다 확인했는데 스택에 괄호가 남아있다는 뜻은 그 괄호는 짝을 못 찾은걸로 판단하면 되겠죠 !?

 

마치 저처럼...

커플 지옥

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if s == "": return True
        stack = []
        for br in s:
            if br == '(' or br == '{' or br == '[':
                stack.append(br)
            else:
                if stack: br_p = stack.pop()
                else: return False
                if br == ')' and not br_p == '(':
                    return False
                elif br == '}' and not br_p == '{':
                    return False
                elif br == ']' and not br_p == '[':
                    return False
        else:
            if stack: return False
            else: return True
                    

요렇게 푸시면 되는데

 

하드코딩이 너무 꼴보기 싫더라고요. LeetCode와 취지도 맞지 않은거 같고요. 그래서 닫는 괄호 확인 시 dictionary를 이용해서 보다 깔끔하게 만들었습니다.

 

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if s == "":
            return True
        stack = []
        dic = {')':'(', ']':'[', '}':'{'}
        for br in s:
            if br == '(' or br == '{' or br == '[': 
                stack.append(br)
            else:
                if stack == [] or dic[br] != stack.pop():
                    return False
        else:
            if stack: return False
            else: return True
                    

보다 확 줄었쥬?

---

이상 20. Valid Parentheses였습니다. ^_^