LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: ( , ) 로만 이루어진 문자열 s
2. output: 주어진 문자열의 부분 문자열 중 가장 긴 유효한 괄호 문자열 길이 리턴
   • 0 <= s.length <= 3 * 104
   • s[i] is '(', or ')'.

Idea

괄호의 유효한 구간 검사 → Stack

해당 문제는 유효한 구간 검사와 더불어 연속된 유효한 구간의 최대길이를 구해야한다.

→ 유효한 구간 카운팅을 추가로 해주면 된다.

Solution

1. 스택으로 유효한 구간 체크

   Stack으로 괄호의 유효 체크

   Boolean으로 체크한 유효구간의 연속된 최대길이 카운팅

   import java.util.*
   
   class Solution {
       fun longestValidParentheses(s: String): Int {
           // 유효한 구간 체크용
           val valid = Array<Boolean>(s.length) { false }
           // 괄호 저장 스택
           val idxStack = LinkedList<Int>()
           for (i in s.indices) {
               val c = s[i]
               if (c == '(') { // 여는 괄호 스택에 인덱스 삽입
                   idxStack.offerLast(i)
               } else { // 닫는 괄호
                   if (idxStack.size > 0) { // 유효한 경우
                       for (j in idxStack.pollLast()..i) { // 해당 구간 체크
                           valid[j] = true
                       }
                   }
               }
           }
           var answer = 0
           var cnt = 0
           // 연속된 유효한 구간 카운팅
           for (boolean in valid) {
               if (boolean) cnt++
               else {
                   answer = Math.max(answer, cnt)
                   cnt = 0
               }
           }
           return Math.max(answer, cnt)
       }
   }
   

   시간 복잡도: 문자열 순회(괄초 유효 검사) + 유효 배열 순회(최장 길이 카운팅) = n

   

Point