[자바스크립트] 괄호 회전하기

Lv. 2. 괄호 회전하기

문제

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

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

 

 

입출력 예

s	result
"[](){}"	3
"}]()[{"	2
"[)(]"	0
"}}}"	0

 

 

자료구조

① 문자열: s

② 정수: result, top

③ 정수형 배열: stack

 

 

알고리즘

① 유효한 괄호 문자열 검사 (isValid 함수):

• stack을 사용하여 여는 괄호를 저장하고, 닫는 괄호를 만날 때 매칭되는 여는 괄호가 있는지 검사한다.
• 만약 매칭되는 여는 괄호가 있으면 stack에서 제거(pop())하고, 그렇지 않으면 false를 반환한.
• 문자열을 모두 검사한 후 stack이 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환한다.

② 회전된 문자열 검사 (solution 함수):

• 문자열 s의 길이만큼 반복하여 각 회전(이동)된 형태를 생성한다.
• 각 회전된 형태를 isValid 함수로 검사하여 유효한 경우 result를 증가시킨다.
• 모든 회전된 문자열을 검사한 후 result를 반환한다.

 

 

소스 코드 

function isValid(s) {
  const stack = [];

  for (const char of s) {
    if (char === "[" || char === "(" || char === "{") {
      stack.push(char);
    } else {
      if (stack.length === 0) return false;

      const top = stack[stack.length - 1];
      if (
        (char === "]" && top === "[") ||
        (char === ")" && top === "(") ||
        (char === "}" && top === "{")
      ) {
        stack.pop();
      }
    }
  }
  return stack.length === 0;
}

function solution(s) {
  let result = 0;
  for (let i = 0; i < s.length; i++) {
    const rotated = s.slice(i) + s.slice(0, i);

    if (isValid(rotated)) {
      result++;
    }
  }

  return result;
}

 

 

 

✔ 출처

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