[Javascript] 프로그래머스 - 괄호 회전하기

문제 설명

주어진 문자열 s가 대괄호 [], 중괄호 {}, 소괄호 ()로 이루어져 있을 때, 이를 왼쪽으로 x(0 ≤ x < s의 길이) 칸 회전했을 때 올바른 괄호 문자열이 되는 x의 개수를 구하는 문제입니다.

올바른 괄호 문자열은 다음 규칙을 따릅니다.

1. (), [], {}는 올바른 괄호 문자열입니다.
2. 올바른 괄호 문자열 A가 있다면, (A), [A], {A} 또한 올바른 괄호 문자열입니다.
3. 올바른 괄호 문자열 A와 B가 있다면, AB 또한 올바른 괄호 문자열입니다.

---

제한 사항

• s의 길이는 1 이상 1,000 이하입니다.

---

해결 방법

알고리즘: 스택, 문자열 회전

1. 올바른 괄호 문자열 판별
   • 스택을 이용하여 괄호가 올바르게 짝을 이루는지 확인합니다.
   • 여는 괄호는 스택에 push하고, 닫는 괄호가 나오면 스택의 top과 비교하여 일치하면 pop합니다.
   • 모든 문자를 검사한 후 스택이 비어있다면 올바른 괄호 문자열입니다.
2. 문자열 회전 및 검증
   • 문자열을 0부터 s.length - 1까지 왼쪽으로 회전하면서 올바른 괄호 문자열인지 판별합니다.
   • 매 회전마다 맨 앞 문자를 제거하고 끝에 추가하여 새로운 문자열을 생성합니다.
   • 올바른 괄호 문자열이면 카운트를 증가시킵니다.

---

시간 복잡도

• isValid 함수의 연산은 O(N)
• 최대 N번의 회전을 수행하므로 전체 시간 복잡도는 O(N²)
• N ≤ 1,000 이므로, 최악의 경우에도 실행이 가능합니다.

---

구현 코드

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

  for (let char of s) {
    if (char === "(" || char === "[" || char === "{") {
      stack.push(char);
    } else if (stack.length > 0 && stack[stack.length - 1] === pairs[char]) {
      stack.pop();
    } else {
      return false;
    }
  }

  return stack.length === 0;
}

function solution(s) {
  let count = 0;
  const size = s.length;

  for (let i = 0; i < size; i++) {
    if (isValid(s)) count++;
    s = s.slice(1) + s[0];
  }

  return count;
}