[LeetCode] 678. Valid Parenthesis String (Daily Question)

문제

---

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:
    - Any left parenthesis '(' must have a corresponding right parenthesis ')'.
    - Any right parenthesis ')' must have a corresponding left parenthesis '('.
    - Left parenthesis '(' must go before the corresponding right parenthesis ')'.'*' 
    - could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

 

문자열 s가 주어졌을 때 괄호짝이 맞는 지 판단하는 문제이다.

여기서 '*'은 필요에 따라 여는괄호, 닫는괄호, 비어있음을 의미한다.

 

예를 들면 "*)"이 주어졌을 때 *이 (역할을 해 줄 수 있기 때문에 True를 반환한다.

Example 1:
Input: s = "()"
Output: true

Example 2:
Input: s = "(*)"
Output: true

Example 3:
Input: s = "(*))"
Output: true

---

 

풀이

---

아이디어

문자열을 앞에서부터 살펴보며 *을 세고, 열린괄호보다 닫힌괄호가 많아질 경우 *을 소모한다.

그리고 뒤에서부터 살펴보며 닫힌괄호와 열린괄호를 바꾸어 생각한다.

 

코드

class Solution:
    def checkValidString(self, s: str) -> bool:
        cnt = 0
        spare = 0
        
        # 앞에서부터 살펴봄
        for c in s:
            # (, ), * 개수 카운트
            if c == '(': cnt += 1
            elif c == ')': cnt -= 1
            else: spare += 1
                
            # (보다 )가 많아질 경우 *을 소모
            if cnt < 0:
                spare -= 1
                cnt += 1
                
            if spare < 0: return False
            
        if spare < cnt: return False
        
        cnt = 0
        spare = 0
        
        # 뒤에서부터 살펴봄
        for c in s[::-1]:
            if c == ')': cnt += 1
            elif c == '(': cnt -= 1
            else: spare += 1
                
            if cnt < 0:
                spare -= 1
                cnt += 1
            
            if spare < 0: return False
        
        return True

 

---

 

후기

---

난이도

아이디어만 떠올리면 구현은 어렵지 않은 문제인 듯 하다.