Longest Valid Parentheses | LeetCode 32

🤔 문제 : Longest Valid Parentheses | LeetCode 32

문제: https://leetcode.com/problems/longest-valid-parentheses/
문제에서 말하는 Valid Parenntheses는 괄호가 열린만큼 잘 닫힌 형태의 문자열이다.

• () : valid
• )( : invalid
• (() :invalid
• ()) :invalid
• (()()) : valid텍스트

어떤 문자열이 주어졌을 때 그 안에서 가장 긴 valid parentheses의 길이를 찾는 문제이다.

💡 풀이

접근 - valid parentheses는?

valid parentheses를 판단하는 방법으로는 문자열을 읽어나가며 stack에 ( 이 나오면 push, )이 나오면 pop을 하는 직관적인 풀이를 떠올릴 수 있다.

하지만 좀 더 고민해보니(와 )의 갯수만으로도 valid parentheses여부를 확인할 수 있다는 생각이 들었다.
왼쪽부터 읽어나가며 )이 (보다 갯수가 많은 순간이 있으면 invalid parentheses이며,
끝까지 읽었을 때 (와 )의 갯수가 같으면 valid parentheses이다.

• ()() => valid
  ( : 1122
  ) : 0112
• )()( => 첫번째 글자까지 읽었을 때 )가 (보다 많으므로 invalid
  ( : 0112
  ) : 1122

이를 바탕으로 isValid라는 함수를 먼저 작성했다.

// s : 주어진 문자열
// stIdx, edIdx : 보고자 하는 substring의 시작/끝index
// leftCount, rightCount : (와 )의 갯수
var isValid = function(s, stIdx, edIdx, leftCount, rightCount){
  if(s[stIdx] === "(") leftCount++;
  else if(s[stIdx] === ")") rightCount++;
  if(rightCount > leftCount) return false;
  if(stIdx === edIdx) return leftCount === rightCount;
  return isValid(s, stIdx+1, edIdx, leftCount, rightCount)
}

1. 모든 substring에 대해서 valid parentheses 여부 판단

어떤 문자열 안에서 가장 긴 parentheses를 찾는 가장 단순한 방법은 아래와 같다.

• 그 문자열의 모든 substring을 구함
• 모든 substring에 대한 valid여부를 판단
• valid할 경우 그 길이를 max값과 비교하고 더 길다면 max 값 업데이트

var longestValidParentheses = function(s) {
    const n = s.length;
    let longest = 0;
    // n*(n-1) 개의 substring에 대해서 모두 validParentheses Check
    for(var i = 0; i<n; i++){
      for(var j = i+1; j< n; j++){
        if(isValid(s, i, j, 0, 0)){
          if(longest< j-i+1){
            longest = j-i+1;
          }
        }
      }
    }
    return longest;
};

var isValid = function(s, stIdx, edIdx, leftCount, rightCount){
  if(s[stIdx] === "(") leftCount++;
  else if(s[stIdx] === ")") rightCount++;
  if(rightCount > leftCount) return false;
  if(stIdx === edIdx) return leftCount === rightCount;
  return isValid(s, stIdx+1, edIdx, leftCount, rightCount)
}

Time Complexity
길이 N짜리 문자열의 모든 substring에 대해 문자열 전체를 탐색한다면
1xN + 2x(N-1) + 3x(N-2) ... +Nx1 -> O(N^3)
Space Complexity
O(1)

대충 생각해도 T.C가 너무 크고, 불필요한 substring까지 보고 있을 것 같다.
제출해보면 당연히 TLE.

TLE가 나올 것 같은 답안이라도 일단 답이 나오도록 작성해보는게 좋다고 생각한다.
처음부터 TLE피해가려고 효율적으로 짜다 보면 오히려 생각이 꼬여서 답이 안나오는 경우가 많았다..

2. 불필요한 substring은 pass

아래 두가지 경우를 pass하도록 했다.
1. 현재까지의 최대 길이보다 짧은 substring
2. substring의 (와 ) 길이가 같지 않은 substring
2번을 위해서 string이 처음 들어올 때 각 자리마다 지금까지 몇개의 (와 ) 가 나타났는지 caching해두어 substring의 (와 ) 의 길이를 빠르게 구할 수 있게 했다.

var longestValidParentheses = function(s) {
    const n = s.length;
  
    // 지금까지 몇개의 `(`와 `)` 가 나타났는지 caching
    const cacheOpen = [];  
    const cacheClose = []; 
    cacheParentheses(s, cacheOpen, cacheClose);

    let longest = 0;
    // n*(n-1) 개의 substring에 대해서 모두 validParentheses Check
    for(var i = 0; i<n; i++){
      for(var j = i+1; j< n; j++){
        // unnecessary case 1 : 어차피 최댓값보다 작게 나올 것
        if(longest > j-i+1) continue;

        // unnecessary case 2 : '('와 ')'의 갯수가 같지 않으면 어차피 invalid
        if(!isValidLength(i, j, cacheOpen, cacheClose)) continue;

        if(isValid(s, i, j, 0, 0)){
          if(longest< j-i+1){
            longest = j-i+1;
          }
        }
      }
    }
    return longest;
};

var isValid = function(s, stIdx, edIdx, leftCount, rightCount){
  if(s[stIdx] === "(") leftCount++;
  else if(s[stIdx] === ")") rightCount++;
  if(rightCount > leftCount) return false;
  if(stIdx === edIdx) return leftCount === rightCount;
  return isValid(s, stIdx+1, edIdx, leftCount, rightCount)
};

var cacheParentheses = function(s, cacheOpen, cacheClose) {
    var open = 0;
    var close = 0;
    for(var i = 0; i <s.length; i++){
        if(s[i] === "(") open++;
        else close ++;
        cacheOpen[i] = open;
        cacheClose[i] = close;
    }
};

var isValidLength = function(i, j, co, cc) {
  if(i === 0) return co[j] === cc[j]
  return co[j]-co[i-1] === cc[j]-cc[i-1]
};

이 정도만 해도 TLE는 면한다 ^^
하지만 아주 좋은 풀이는 아닌지 같은 js안에서 꽤나 하위권이다..

 

3. O(N) Solution

Discussion에 O(N)짜리 C++ solution이 있어서 js 로 옮겨봤다.

()(()()))()()

이 문자열의 lvp(longest valid parentheses)를 구하려면 valid parentheses가 끊기는 인덱스를 표시해두어야 한다.
()(()()(()()

있을 때, 문자열을 앞에서부터 읽으면서

• (일 때는 stack.push(index)
• )인데 바로 직전 문자가 (일 때는 바로 stack.pop()
• )인데 바로 직전 문자가 (이 아닐 때는 stack.push(index)
• 문자열 다 읽은 후 stack의 맨 아래에 -1, 맨 위에 string.length를 추가

하는 방식으로 stack을 구성하고 나면, stack에는 valid parentheses가 끊기는 인덱스만 저장되어 있게 되고,
stack에서 인접한 숫자끼리의 차이-1의 최댓값이 lvp가 되는 것이다.

예를들어,
이 방식대로 위 문자열 ((()())() 에 대해 stack의 모습을 그려보면

인접한 숫자끼리의 차이-1 은 0, 8이 되고, 따라서 최대값은 8이 된다.

var longestValidParentheses = function(s) {
    const n = s.length;
    const stack = [];

    for(var i = 0; i<n; i++){
      if(s[i] === "(") stack.push(i);
      else if(s[i] === ")"){
        if(stack.length > 0 && s[stack[stack.length-1]] === "(") stack.pop()
        else stack.push(i)
      }
    }

    // ex1) )))()()((  => [-1, 0, 1, 2, 7, 8, 9]
    // ex2) ()) => [-1, 2, 3]
    stack.unshift(-1)
    stack.push(n)
    return stack.length>1 ? stack.reduce((acc, cur, idx) => cur - stack[idx-1]-1 > acc ? cur - stack[idx-1]-1 : acc, 0) : n;
};

Time Complexity
길이 N짜리 문자열을 한번만 탐색하므로 O(N)
Space Complexity
stack의 최대 길이는 N이므로 O(N)

(훔쳐온 풀이긴 하지만) 꽤나 좋은 결과로 통과하였다 😊

문자열을 한 번 읽으면서 valid가 끊어지는 지점을 파악할 수 있다는건 생각도 못했는데.. 멋진 풀이였다.