All Articles

Longest valid parentheses

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의 길이λ₯Ό κ΅¬ν•œλ‹€.

Published Mar 29, 2020

If I keep marking the dots, someday they will πŸ”—πŸ”—