Valid Parentheses

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

Valid Parentheses - LeetCode

문제설명:

문자에 () [] {} 이렇게 제거해나가서 대칭이 모두 맞으면 true 대칭이 하나라도 맞지 않는 것이 있다면 false로 출력

 

방법: 스택으로 구현해보자

받은 문자열은 for문으로 반복

 

1. 여는 괄호("(", "[", "{" ) 를 만나면 stack에 append 해준다.

2. 닫는 괄호(")", "]", "}") 를 만나면 stack.pop()을 해 닫는 괄호와 매칭되는게 있는지 체크한다. 있으면 pop()만 해주면 됐기때문에 append 없이 continue

 

* 참고 : python은 list가 스택역할을 흉내낼수 있다.

        for s in strs:
            if s == "(" or s == "{" or s == "[":
                stack.append(s)

1. 여는 괄호("(", "[", "{" ) 를 만나면 stack에 append 해준다.

 

        for s in strs:
            if s == "(" or s == "{" or s == "[":
                stack.append(s)
                
            # 닫는 괄호가 들어온 경우
            else:
                tmp = stack.pop()
                if s == "}" and tmp == "{":
                    continue
                if s == ")" and tmp == "(":
                    continue
                if s == "]" and tmp == "[":
                    continue
                else:
                    stack.append(tmp)
                    stack.append(s)

2. 닫는 괄호가 들어온 경우 

    - 전에 스택에 있었던 요소를 pop해 현재 받아온 문자(s) 와 비교한다.

    - 만약 매칭되는 문자가 있으면 이미 append, pop 진행없이 다음 원소를 비교한다.

    - 매칭되는 문자가 없으면 기존 pop을 했던 원소를 다시 넣어주고(처음 요소) 그 다음으로 받아온 원소(s)를 스택에 넣어준다.

 

        if len(stack) == 0:
            return "true"
        else:
            return "false"

3. 마지막으로 스택의 길이를 확인한다.

    - 스택의 길이가 0 이면 매칭되는 원소가 있어 남아있는게 없기때문에 true 를 반환

    - 길이가 0이 아니라면 매칭이 되지 않은 원소가 남아있어 false 를 반환한다.

 

 

---

                if s == "}" and tmp == "{":
                    continue
                if s == ")" and tmp == "(":
                    continue
                if s == "]" and tmp == "[":
                    continue

이 코드 부분을 뭔가 좀 더 간결하게 해보고 싶었다. 

switch는 한 원소를 case로 비교하기 때문에 길이가 비슷해질거 같았다.

dictionary 을 Key, Value로 구분을 해보자

 

딕셔너리 활용

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

if s == "}" and tmp == "{":                     continue                 if s == ")" and tmp == "(":                     continue                 if s == "]" and tmp == "[":                     continue

tmp = stack.pop if pair[s] == tmp:      continue

 

시간을 측정해보자

1.7881393432617188e-05

2.002716064453125e-05

딕셔너리로 찾을 시 시간이 좀 더 걸린다.

 

전체코드

import time
class Solution:
    def isValid(self, strs):
        pair = {
            "}": "{",
            "]": "[",
            ")": "(",
        }
        stack = []
        for s in strs:
            if s == "(" or s == "{" or s == "[":
                stack.append(s)
            else:
                tmp = stack.pop()
                if pair[s] == tmp:
                    continue
                else:
                    stack.append(tmp)
                    stack.append(s)
        if len(stack) == 0:
            return "true"
        else:
            return "false"

start_time = time.time()
s = "(]"
#s = "()[]{}"
print(Solution().isValid(s))

end_time = time.time()
print("실행 시간 = ", end_time - start_time)