출처

https://school.programmers.co.kr/learn/courses/30/lessons/76502

최초 풀이

괄호 검사는 보통 스택을 활용하는 데, 직관적인 방법으로 풀어보았다.

const isValid = (s) => {
    const arr = ['[]', '{}', '()']

    for (let i=0; i<s.length-1;) {
        const temp = s[i] + s[i+1]
        if (arr.includes(temp)) {
            s = s.substring(0, i) + s.substring(i+2, s.length)
            if (i!==0) i --
        }
        else {
            i ++
        }
    }

    return s? false : true
}

function solution(s) {
    var answer = 0;

    for (let i=-1; i<s.length-1; i++){
        s = s.substring(1, s.length+1) + s.substring(0, 1)
        // console.log(s)

        if (isValid(s)) answer ++

    }

    return answer;
}

시간복잡도는 최악의 경우 n^3이기 때문에, 효율성 개선된 코드로 다시 작성했다.

개선된 풀이

function isValid(s) {
  const stack = [];
  const pairs = {
    ")": "(",
    "}": "{",
    "]": "[",
  };

  for (const c of s) {
    if (c === "(" || c === "{" || c === "[") {
      stack.push(c);
    } else if (c === ")" || c === "}" || c === "]") {
      if (stack.length === 0 || stack.pop() !== pairs[c]) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

function solution(s) {
  let answer = 0;
  const n = s.length;

  for (let i = 0; i < n; i++) {
    if (isValid(s)) {
      answer++;
    }

    s = s.substring(1) + s[0];
  }

  return answer;
}

stack을 사용해 isValid 함수가 O(n)으로 개선되었다. 총 n^2

솔루션 비교

• 첫 번째 코드는 문자열 조작을 사용하여 유효한 괄호 쌍을 찾아 제거한다.
• 두 번째 코드는 스택 자료구조를 사용하여 괄호의 유효성을 검사한다.
• 두 번째 코드가 첫 번째 코드보다 시간 복잡도가 개선되어 더 효율적이다. n^3 -> n^2