javaScript 괄호 회전문제 해결하기

문제

문자열 s를 왼쪽으로 회전시켰을 때, 얼마나 많은 경우에 해당 문자열이 올바른 괄호 문자열이 되는지 계산하여라

풀이 

function solution(s) {
  const getIsCorrectString = (stringsArr) => {
    const correctSet = { ']': '[', ')': '(', '}': '{' };
    const stack = [];
    let isCorrectString = true;

    stringsArr.forEach((str) => {
      if (str in correctSet) {
        if (correctSet[str] === stack.at(-1)) stack.pop();
        else isCorrectString = false;
      } else {
        stack.push(str);
      }
    });

    return stack.length === 0 && isCorrectString;
  };

  let answer = 0;
  for (let i = 0; i < s.length; i++) {
    const changedS = [...s.slice(i), ...s.slice(0, i)];
    const isCorrectString = getIsCorrectString(changedS);
    answer += isCorrectString ? 1 : 0;
  }

  return answer;
}

• getIsCorrectString 
  •  주어진 문자열 배열이 올바른 괄호 문자열인지 확인하는 방법
  • Set 객체를 활용해 각 닫는 괄호에 대한 올바른 여는 괄호 매핑
  • stack : 배열을 사용하여 여는 괄호를 추적하고, 닫는 괄호 만날 때마다 비교하여 올바른지 확인
• forEach 
  • 문자열 배열 순회
  • str이 correctSet에 속하는지 확인
  • 만약 str이 correctSet에 속하면, 스택의 맨 위에 있는 괄호와 쌍을 이루는지 확인. 쌍을 이루면 스택제거 그렇지 않으면 false로 설정
  • 속하지 않는 경우 (왼쪽 괄호인 경우) 스택에 추가

 

다른 풀이

function solution(s) {
    if(s.length % 2 === 1) return 0;

    let answer = 0;
    const mapping = { "}" : "{", "]" : "[", ")" : "("};

    for(let i = 0; i < s.length; i++) {
        const stack = [];
        const rotate = s.slice(i) + s.slice(0, i);
        let flag = true;

        for(let j = 0; j < s.length; j++) {
            if(rotate[j] === "[" || rotate[j] === "(" || rotate[j] === "{" )
                stack.push(rotate[j]);
            else {
                const last = stack.pop();
                if(last !== mapping[rotate[j]]) {
                    flag = false
                    break;
                }
            }
        }

        if(flag) answer++;
    }

    return answer;
}

• 문자열 길이 홀수인 경우 바로 0 반환 
• answer : 올바른 괄호 문자열의 경우 수를 저장하는 변수
• mapping : 괄호 매핑 객체
• 각 회전별로 스택을 초기화 
• 현재 인덱스 i를 기준으로 문자열을 회전시킨다 내부 반복문을 통해 회전된 문자열에 대한 괄호를 확인하며 스택을 사용하여 올바른 괄호 문자열인지 판별
• true인 경우에만 answer 증가

function solution(s) {
  let answer = 0;
  for (let i = 0; i < s.length; i++) {
    const arr = [];
    const temp = i === 0 ? s : s.slice(i) + s.slice(0, i);
    for (let j = 0; j < temp.length; j++) {
      if (arr[arr.length - 1] === '(' && temp[j] === ')') arr.pop();
      else if (arr[arr.length - 1] === '[' && temp[j] === ']') arr.pop();
      else if (arr[arr.length - 1] === '{' && temp[j] === '}') arr.pop();
      else arr.push(temp[j]);
    }
    if (arr.length === 0) answer++;
  }
  return answer;
}