[프로그래머스] Lv.2 괄호 회전하기 - JavaScript

괄호 회전하기

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

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 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의 괄호 문자를 왼쪽으로 한 칸씩 밀고, 맨 앞의 괄호 문자를 맨 뒤로 보내면 된다.
괄호의 짝 맞추는 과정을 생각해보면

1. 여는 괄호가 나오면 stack에 push를 한다.
2. 그리고 그거랑 맞는 닫는 괄호가 나오면 pop을 한다.
3. 닫힌 괄호가 나왔는데 스택의 길이가 0이면 실패를 반환한다.
4. 짝이 안맞아도 실패를 반환한다.
5. 마지막에 true이면서 스택의 길이가 0 이면 즉 모든 괄호가 상쇄되었다는 얘기이므로 카운트 값을 1 증가시킨다.

이런식으로 과정을 접근하였다. 

 

제출한 코드

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

  for (let i = 0; i < n; i++) {
    const stack = [];
    let isCorrect = true;

    for (let j = 0; j < n; j++) { // 회전시키면서 참조한다.
      const c = s[(i + j) % n];

      if (c === "[" || c === "(" || c === "{") { // 만약 열린 괄호가 나오면 푸쉬한다.
        stack.push(c);
      } else { // 닫힌 괄호가 나왔을 때
        if (stack.length === 0) { // 길이가 0이면, 그냥 실패이므로 false 반환
          isCorrect = false; 
          break;
        }
        const top = stack[stack.length - 1]; // top 값은 length-1의 인덱스에 위치
        if (
          (c === "]" && top === "[") ||
          (c === ")" && top === "(") ||
          (c === "}" && top === "{")
        ) {
          stack.pop();
        } else {
          isCorrect = false; 
          break;
        }
      }
    }

  
    if (isCorrect && stack.length === 0) { // 만약 true 이고 모든 괄호가 상쇄됐다.
      answer++;
    }
  }

  return answer;
}

 

사실상 다른 부분은 어렵지 않았기 때문에 제일 고민을 많이 했던 부분은 const c = s[(i+j)%n] 이 부분이다. 

문자열을 왼쪽으로 회전시킨 것처럼 인덱스를 참조하는 방식이다.

 

문자열은 인덱스의 0부터 n-1 까지만 존재하게 되는데, 회전을 하다 보면 인덱스가 n 이상으로 넘어가 버리기에

%n 연산을 하여서 원본 문자열의 인덱스를 가져오게 하여 문자열의 끝을 넘어가면 다시 처음으로 돌아오게 하였다.

이렇게하면 별도의 회전 문자열을 만들지 않아도 마치 회전한 것처럼 참조할 수 있다.

 

다른 사람의 풀이

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;
}

 

slice를 이용하여서 직접 회전 문자열로 만든 풀이도 있었다.

예를들어서 s가 abcd라고 치고 i가 2라고 하면 cd + ab 로 cdab가 만들어서 새롭게 회전 문자열이 만들어진다. 

이 풀이가 훨씬 더 간단한 것 같기도 하다...! 다음에 비슷한 문제가 나오면 이런식으로 한번 접근해봐야겠다.