Valid Parentheses

출처

https://leetcode.com/problems/two-sum/

문제

Given a string containing just the characters '('')''{''}''[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

예시

Input: "()"
Output: true

Input: "()[]{}"
Output: true

Input: "(]"
Output: false

Input: "([)]"
Output: false

답1

class Solution:
    // 재귀적으로 검사를 하는데, 중간에 있는게 딱 끝나고, 그 다음거를 해야하는데 그때 그 다음께 어디인지를 position으로 지정한다
    position = 0
    // 아래처럼 하면 절댓값을 사용해서 '('와 ')'를 하나의 1이라는 그룹으로 묶을 수 있다. 그리고 비교하기도 쉬워진다.
    sToNumDic = {
        '(' : 1,
        ')' : -1,
        '{' : 2,
        '}' : -2,
        '[' : 3,
        ']' : -3
    }
    def isValid(self, s: str) -> bool:
        // 문제에서 "" 빈 스트링도 True라고 했으니까 설정해준다
        if (len(s) == 0) :
            return True
        // 짝이 안맞는 경우는 무조건 False
        if (len(s)%2 == 1):
            return False
        
        self.s = s
        // 재귀적으로 실시!!
        return self.isClosedWell(self.sToNumDic[s[0]])
    
    def isClosedWell(self, openNum: int) -> bool:
        // 포지션에 1을 더해서, 다음 기호가 닫힌 기호인지 판단한다
        self.position = self.position + 1
        // 닫히는거('}') 없이 계속 열리기만('{') 해버리면 계속 position만 늘어나기 때문에 이를 방지하기 위해서 검사해준다
        if ( self.position == len(self.s) ) :
            return False
        // sToNumDic에서 문자를 숫자로 얻어온다. 일단 이게 닫히는 기호라고 가정했기 때문에 변수 이름이 closeNum이다
        closeNum = self.sToNumDic[self.s[self.position]]
        // 0보다 작으면 어쨋든 닫히려고 하고 있다는 말이다
        if (closeNum < 0) :
            // 절대값이 달라버리면 '(' 이렇게 열리고 '}' 이렇게 닫히는 거니까 False
            if (openNum != abs(closeNum)) :
                return False
            // 아니면 제대로 닫힌거니까 True
            else :
                return True
        // closeNum이 양수라면! 새로 열린거니까
        else :
            // 한번더 재귀적으로 호출해준다.
            result = self.isClosedWell(closeNum)
            // 제대로 닫혔으면
            if (result) :
                // 그 다음께 있는지 계속 검사한다. 여기서 True가 될 수도 있고, False가 될 수도 있다. False가 나와버리면, 그 다음놈은 제대로 안닫혔다는 말이다. True가 나오면, 일단은 잘 닫혔다는 말이지만, 그 다다음 놈이 제대로 안닫혔는지는 보장 못한다. 계속 재귀적으로 검사해야한다. 만약에 계~속 True가 나오면, 모든게 제대로 열리고 닫힌것이다.
                result = self.isClosedWell(openNum)
            return result

답2

class Solution:
    // 열리고 닫히는 쌍을 미리 지정해놓는다
    char_mapping = {
        "(" : ")",
        "{" : "}",
        "[" : "]"
    }
    def isValid(self, s: str) -> bool:
        // 열리고 -> 열리고 -> 열리고 -> 닫히고 -> 닫히고 -> 닫히고...맨 먼저 열린게 맨 마지막에 닫혀야지. 스택 느낌이 들잖아. 맨 처음들어간놈이랑 맨 마지막에 chractor랑 비교해야되니까 stack이 어울려.
        stack = []
        for c in s :
            // c가 열린놈이라면
            if (self.char_mapping.get(c)) :
                // 스택에 추가하라 이거야. 왜냐면 나중에 닫히는 놈이랑 지금 쌓이는 놈이랑 비교해줘야하거든. 순서에맞게.
                stack.append(self.char_mapping[c])
            // 스택에 쌓인게 없다? 그러면 처음부터 )]} 이꼴이 난거지. 왜냐, 처음엔 당연히 열려야 되고, 열렸으면 스택에 쌓였을테고 그러면 스택이 비어있을리가 없으니까. 즉, 비어있다는 뜻은 처음부터 닫혔다는거야.

            // stack.pop() 했는데 지금 c랑 다르다? 스택으로 관리했기 때문에 짝이 딱딱 맞아떨어져야하는데 지금 pop한게 다르다는거는, 짝이 안맞다는거야.
            // [ ( [ } ) ] 팝을 했을때 (세번째 '[' 가 있었기 때문에) ']' 가 나와야 하는데 뜬금없이 '}' 가 나왔기 때문에 False야!
            elif (len(stack) == 0 or stack.pop() != c):
                return False
        // 스택에 쌓인게 없이 짝이 잘 맞아 떨어져서 모두 pop되었다면 True고 뭔가 짝이 안맞아서 남는게 있다면 false야.
        return len(stack) == 0

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다