2021-01-20] Valid Parentheses

오늘의 문제:

leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/581/week-3-january-15th-january-21st/3610/

 

문제 예시를 보며 설명해보자.

문제예시 1-5

입력값으로 주어지는 문자열은 소, 중, 대 괄호만으로로 이뤄진다.

주어진 값에 대해서 괄호가 잘 닫혔는지, 이상은 없는지 확인하는 문제이다.

각 괄호들로 알맞게 닫혀져있는지 확인하여 참 ,거짓을 판별하자.

 

먼저, 실패조건을 생각해본다.

1) 주어진 문자열의 길이는 무조건 짝수여야한다. ( 쌍으로 열고 닫히기 때문에 )

if len(s)%2==1: # 주어진 s의 길이가 홀수면 False
    return False

 

2) 닫히는 괄호가 먼저 나오면  무조건 실패 ( 예시 -> '][()()', 먼저 열려야해서 실패 )

if not openl: # openl은 열린 괄호를 저장하는 변수, 열린 괄호를 만나기 전 닫힌 괄호를 만나면 False
    return False

 

3) 마지막으로 열려진 괄호와 닫히는 괄호의 종류가 다르면 실패 ( 3,4 예시 )

data=openl.pop() # 마지막 열린괄호의 값을 구하고 닫힌괄호와 합쳤을 때 괄호의 종류가 다르면 False
if data+s[i] in ['()','{}','[]' ]: 
    continue
else:
    return False

4) 열린 괄호와 닫힌 괄호의 숫자가 맞지 않으면 실패 ( 예시 -> '[ [ ( ) ]'  )

if openl==[]: # 결과적으로 열린 괄호가 닫힌 괄호와 숫자가 맞게 pop되면 괄호는 더 이상 없음
    return True
else:
    return False

 

이를 구현한 코드로 보자.

 

문제풀이)

class Solution:
    def isValid(self, s: str) -> bool:
        openl=[]
        if len(s)%2==1:
            return False
        else:
            for i in range(len(s)):
                if s[i] in ['{','[','(']:
                    openl.append(s[i])
                else:
                    if not openl:
                        return False
                    data=openl.pop()
                    if data+s[i] in ['()','{}','[]' ]:
                        continue
                    else:
                        return False
        if openl==[]:
            return True
        else:
            return False