[Javascript][Programmers] 괄호 회전하기

 

문제

• 키워드: 문자열 회전, 괄호 짝 맞추기
• 괄호의 짝을 맞출 때, 닫는 괄호가 나오면 바로 직전(top → stack)에 같은 모양의 여는 괄호가 존재해야 한다.

 

나의 풀이

• 시간복잡도: O(N²)

// 문자열 회전
function rotateArr(arr) {
    arr.push(arr.shift());
    return arr;
}

// 괄호 짝 맞추기
function solution(s) {
    let correctCount = 0;
    let bracketArr = [...s]

    for(let i = 0; i < s.length; i++) {
        const bracketStack = [];
        let rotatedBracketArr = rotateArr(bracketArr);
        let correct = true;
        for(const bracket of rotatedBracketArr) {
            if(bracket === '(' || bracket === '{' || bracket === '[') {
                bracketStack.push(bracket)
            } else {
                if(bracketStack.length === 0) {
                    correct = false;
                    break;
                }
                const top = bracketStack.length - 1;
                else {
                    if(bracket === ')' && bracketStack[top] === '(') {
                        bracketStack.pop();
                    } else if(bracket === '}' && bracketStack[top] === '{') {
                        bracketStack.pop();
                    } else {
                        if(bracketStack[top] === '[') bracketStack.pop();
                    }
                }
            }            
        }
        if(correct && bracketStack.length === 0) correctCount++;
        bracketArr = [...rotatedBracketArr];
    }

    return correctCount;
}

rotateArr 함수는 shift()와 pop()을 이용하여 배열을 한 칸씩 회전시키고, solution 함수는 주어진 문자열의 각 회전에 대해 스택을 이용하여 괄호의 짝이 맞는지 확인합니다. 여는 괄호는 스택에 추가하고, 닫는 괄호를 만나면 스택의 top과 비교하여 짝이 맞으면 pop합니다. 모든 괄호를 확인한 후 스택이 비어있으면 올바른 괄호 문자열로 간주하고, 이러한 경우의 수를 세어 최종적으로 반환합니다. 이 과정을 문자열의 길이만큼 반복하여 모든 회전 경우를 검사합니다.

 

문제점

• shift() 사용으로 인한 큰 연산 비용 → 시간 복잡도: O(n)
• 문자열 s를 배열로 복사하는 과정에서의 추가적인 연산 → 시간 복잡도: O(n)

 

다른 풀이

• 시간복잡도: O(N²)

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

  for (let i = 0; i < s.length; 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) {
          // ➌ 여는 괄호가 없는 경우
          isCorrect = false;
          break;
        }

        // ➍ 닫힌 괄호는 스택의 top과 짝이 맞는지 비교
        const top = stack[stack.length - 1];
        if (c === "]" && top === "[") {
          stack.pop();
        } else if (c === ")" && top === "(") {
          stack.pop();
        } else if (c === "}" && top === "{") {
          stack.pop();
        } else {
          isCorrect = false;
          break;
        }
      }
    }

    // ➎ 모든 괄호의 짝이 맞는 경우
    if (isCorrect && stack.length === 0) {
      answer += 1;
    }
  }

  return answer;
}

전체적인 풀이는 유사하지만 문자열 회전을 구현하는 과정에서 큰 차이가 있습니다.

• 진짜로 문자열을 회전시키면 연산 비용이 많이 들기 때문에 인덱스를 활용
• i: 첫 번째 문자의 위치, j: i 이후에 등장하는 문자들의 위치
• 모듈러 연산을 통해 실제 배열에서의 인덱스 계산

 

---

Reference

코딩테스트 합격자 되기: 자바스크립트 편