[JS] 괄호 회전하기

 

프로그래머스

 

문제 이해

서로 다른 세 가지 괄호가 올바르게 정렬되어야 한다. 괄호가 한 종류만 있는 문제와 달리 다른 종류의 괄호를 어떻게 처리할 것인가 고민해봐야 한다.

한 종류만 있는 경우 `(`을 `1`과 대응하고 `)`을 `-1`과 대응시켜 중간에 합이 음수가 되지 않도록하면 됐지만 이번에는 괄호가 여러 종류가 있어 다른 접근방법을 생각해봐야 한다.

 

방법 1 - 숫자와 대응하기

위에 이야기한 것처럼 숫자와 대응시켜보았다. 문자열의 길이가 최대 1000이므로 1000배씩 차이나면 겹치치 않을 것이라 생각해 `( - 1, { - 1000, [ - 1000000`으로 대응을 시켰지만 `{)` 이런 경우 `999`와 대응되므로 음수가 되지 않았다. 그래서 다른 방법을 찾아보기로 했다

 

방법 2 - 스택

스택을 이용해서 괄호가 한 종류만 있는 문제를 해결한 사람도 많을 것 같다. 이와 마찬가지로 마지막에 추가된 괄호가 현재 괄호와 쌍을 이룬다면 마지막에 추가될 괄호를 제거하고, 다음 괄호로 넘어간다. 만약 괄호가 쌍을 이루지 않는다면 스택에 추가하고 넘어간다. 이렇게 하면 괄호 종류에 상관없이 문제를 해결할 수 있다.

 

const brackets = { "(": 1, ")": -1, "{": 2, "}": -2, "[": 3, "]": -3 };

function solution(s) {
  let answer = 0;

  const len = s.length;
  for (let idx = 0; idx < len; idx++) {
    const tmp = s.slice(idx, len) + s.slice(0, idx);
    // console.log(idx, tmp);

    const stack = [brackets[tmp[0]]];
    for (let i = 1; i < len; i++) {
      if (stack.at(-1) > 0 && brackets[tmp[i]] === -stack.at(-1)) {
        stack.pop();
        // console.log('o', stack)
      } else {
        // console.log(brackets[tmp[i]], -stack.at(-1));
        stack.push(brackets[tmp[i]]);
        // console.log('x', stack)
      }
    }

    // console.log(stack);
    if (stack.length === 0) {
      answer++;
      // console.log("ok", tmp);
    }
  }

  return answer;
}

 

괄호를 숫자와 대응시켰기 때문에 부호가 달라야하는 것 뿐만 아니라 시작하는 괄호, 즉 양수여야하는 것도 예외 처리 시 신경써야 한다.