LeetCode 20(Valid Parentheses, Python)

1. 문제 링크

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

2. 문제 설명

• (){}[]로만 구성된 string이 주어졌을 때 아래 3가지 요건을 다 만족하는지 판단 - True or False 반환
  • 열린 괄호 ( { ] 는 같은 유형의 괄호에 의해 닫혀야 한다.
  • 열린 괄호는 올바른 순서로 닫혀야 한다.
  • 각 닫는 괄호는 동일 유형의 열린 괄호와 대응해야 한다. 
• 예시) "()" true, "()[]{}" true, "(]" false

3. 처음 풀이 

• true인 string은 무조건 [], {}, () 중 하나의형태를 포함하고 있다.
  • 단순하게 열고 닫는 괄호 이웃한 것을 한 쌍 한쌍 삭제하는 구조

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s)%2==1: # len이 홀수이면, 적어도 하나는 쌍을 이루지 못하므로 False 반환
            return False
        for _ in range(len(s)//2): # s에서 (), [], {}를 하나씩 삭제
            s=s.replace('()','').replace('[]','').replace('{}','')
            if len(s)==0: # 다 삭제되어 빈 string이 되면 True 반환
                return True
        if len(s)>0: # 그렇지 않으면 False 반환
            return False
        return True

• runtime이 하위 12.5%로 다른 풀이 탐색 
  • 여는 괄호 list, 닫는 괄호 list를 별도로 보관 후, 
  • for문을 돌리다가, 닫는 괄호를 만나면, 짝꿍이 맞는지 판별 후 하나 씩 삭제

class Solution:
    def isValid(self, s: str) -> bool:
        listOfOpen=['(','[','{']
        closeToOpen={')':'(',']':'[', '}':'{'}
        temp=[]

        if len(s)%2==1: # 홀수이면 적어도 하나는 쌍을 이루지 못하므로 False 반환
            return False
        
        for i in range(len(s)):
            if s[i] in listOfOpen: 
                temp.append(s[i])
            else:
                if len(temp)==0: # temp가 
                    return False
                elif temp[-1]!=closeToOpen[s[i]]: # 가장 마지막 열린괄호가 닫힌괄호와 대응되지 않으면 False 반환
                    return False
                else:
                    del temp[-1]
        
        if len(temp)!=0:
            return False
        else:
            return True

 

4. 다른 풀이 

• 다른 사람의 풀이 중 괜찮았던 풀이
• list.pop()을 하면서 for문 돌 때마다, 값을 삭제하면, 따로 어디에 값을 보관할 필요가 없이, 
• for문을 다 돌린 후, 마지막에 list가 비어있는지 아닌지만 판별하면 된다.

class Solution(object):
	def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        d = {'(':')', '{':'}','[':']'}
        stack = []
        for i in s:
            if i in d:  # 1
                stack.append(i)
            elif len(stack) == 0 or d[stack.pop()] != i:  # 2
                return False
        return len(stack) == 0 # 3

5. 배운 점 

• 이번에도 알고리즘보단 규칙찾기가 중요했다!