<Hard> Longest Valid Parentheses (LeetCode : C#)

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

📕 문제 설명

괄호로 이루어진 문자열 주어질 때 가장 긴 가능한 괄호 문자열의 길이 반환

• Input
  괄호로 이루어진 문자열
• Output
  가장 긴 가능한 괄호 문자열의 길이

예제

풀이

기본적으로 가능한 괄호의 수는 다음과 같이 확인
1) '('의 경우 left count 증가, ')'의 경우 right count 증가
2) 만약 left와 right 개수가 같은 경우 valid 괄호로 판단
3-1) 만약 왼쪽에서 오른쪽 볼 때 오른쪽 괄호 수가 더 많으면 invalid하므로 0으로 초기화 [)(]
3-2) 만약 오른쪽에서 왼쪽으로 볼 때 왼쪽 괄호 수가 더 많으면 invalid하므로 0으로 초기화 [(()]

1. 왼쪽에서 오른쪽을 보면서 가능한 괄호 수 확인
2. 오른쪽에서 왼쪽을 보면서 가능한 괄호 수 확인
3. 최댓값 반환

public class Solution {
    public int LongestValidParentheses(string s) {
     
        int count = 0;
        int left = 0;
        int right = 0;
        // 왼쪽 -> 오른쪽 : 가능한 괄호 수 계산
        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] == '(') left++;
            else right++;

            if (left == right) count = Math.Max(count, left + right);

            if (right > left) left = right = 0;
        }

        left = 0;
        right = 0;
        // 오른쪽 -> 왼쪽 : 가능한 괄호 수 계산
        for (int i = s.Length - 1; i >= 0; i--)
        {
            if (s[i] == '(') left ++;
            else right ++;

            if (left == right) count = Math.Max(count, left + right);

            if (left > right) left = right = 0;
        }

        return count;
        
    }
}

결과

(이것도 시간 의미 x -> 너무 미미함)