[Node.js] 프로그래머스 - 괄호 회전하기

문제

스택 + 문자열

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

문제 풀이

O(N^2) 으로 해결해야 할 듯 하다.

접근

1. 회전을 구현해야 한다
2. 괄호가 유효한지 검사 해야한다.

아! 스택으로 접근하면 되겠군!

의사코드와 설계

Solution : 메인 루프

길이가 홀수인지 확인한다. (홀수 괄호는 짝을 이룰 수 없으니 불가능)

0부터, 주어진 문자열 길이까지 반복

회전 -> s.substring(x)과 s.substring(0,x)를 통해 문자열을 회전시키자

checkCorrect : 검사

스택과 괄호 짝 판단을 위한 매핑 PAIR를 추가

문자열을 순회하며 열린 괄호는 스택에 넣고, 닫힌 괄호가 나온다면 스택과 비교해서 짝이 맞는지 확인 (PAIR 매핑 사용)

순회 후 스택이 전부 비었는지 판단하여 가능 여부를 반환 (true/false)

최종 코드

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

  if (sLen % 2 !== 0) return 0;

  for (let x = 0; x < sLen; x++) {
    const rotated = s.substring(x) + s.substring(0, x);

    if (checkCorrect(rotated)) {
      answer++;
    }
  }
  return answer;
}

function checkCorrect(s) {
  const st = [];
  const PAIRS = {
    ")": "(",
    "]": "[",
    "}": "{",
  };

  for (const char of s) {
    if (char === "(" || char === "[" || char === "{") {
      st.push(char);
    } else if (char === ")" || char === "}" || char === "]") {
      if (st.length === 0) {
        return false;
      }
      const last = st.pop();
      if (last !== PAIRS[char]) {
        return false;
      }
    }
  }
  return st.length === 0;
}

마무리

간만에 다룬 스택. 이전에 문제 풀 때는 괜히 top 이런거랑 하나하나 구현해서 해보려고 했으나, 역시 push() 쓰는편이 훨씬 편하다.

코테를 더욱 빡세게 준비해야 하는 것이 맞는 것 같아서 하나하나 풀어보고 있으나, 쉽지 않다. 하지만 차근차근 하다보면 언젠가 되지 않을까!?

화이팅화이팅!!

-뱅-