https://leetcode.com/problems/longest-valid-parentheses/
λ λ©μλ νμ΄λ μΈν°λ·μ μ°Ύμ보μλ©΄ λ§μλ°β¦ κ°λ¨ν νλ €λ©΄ μ΄λ κ² ν μλ μλ€ μΆμ΄μ μ 리ν΄λ³Έλ€. λ°±κ·ΈλΌμ΄λκ° PSμ μλμ§λΌ λ¨νν μ€λͺ μ΄ μ¬μ΄ νμ΄ λ°μ λͺ»νλ€ γ γ ;
class Solution:
def longestValidParentheses(self, s: str) -> int:
valid_chars = [False for _ in s]
stack = []
for i in range(0, len(s)):
c = s[i]
if c == '(':
stack.append(i)
elif c == ')' and len(stack) != 0:
matching_i = stack.pop()
valid_chars[i] = True
valid_chars[matching_i] = True
elif c == ')' and len(stack) == 0:
pass
longest_valid =0
current_valid = 0
for c in valid_chars:
if c:
current_valid += 1
else:
longest_valid = max(current_valid, longest_valid)
current_valid = 0
longest_valid = max(current_valid, longest_valid)
return longest_valid
μ€νΈλ§μμ β(βκ° validν parenthesesκ° λλ €λ©΄ λμ€μ β)βλ₯Ό λ§λμ κ΄νΈκ° λ«νμΌ νλ€. κ·Έλμ μ€νμ κ°μ§κ³ μν¨μ€λ‘ μ€νΈλ§μ λλ©΄μ κ° κΈμμ validity μ¬λΆλ₯Ό μ μ΄λλλ€.
κ·Έ λ€μμ μ΄μ λ€μ μ validity 리μ€νΈλ₯Ό κ°μ§κ³ κ·Έμ€μμ κ°μ₯ κΈ΄ streakμ κΈΈμ΄λ₯Ό ꡬνλ€.