[프로그래머스] 괄호 변환

문제 설명

균형잡힌 괄호 문자열을 올바른 괄호 문자열로 변환하는 문제를 풀어보자.

알고리즘 규칙:

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리 (u는 더 이상 분리할 수 없고, v는 빈 문자열 가능)
3. u가 "올바른 괄호 문자열"이면 v에 대해 재귀 수행 후 u와 연결
4. u가 올바르지 않으면 특정 변환 과정 수행

핵심 개념 이해

균형잡힌 vs 올바른 괄호 문자열

• 균형잡힌: '('와 ')'의 개수가 같음
• 올바른: 균형잡힌 + 괄호가 올바른 순서로 매칭됨

분리 알고리즘의 핵심

문제에서 가장 헷갈리는 부분은 "더 이상 분리할 수 없는 균형잡힌 괄호 문자열"이다.
쉽게 말해 괄호 쌍이 맞아떨어지는 첫 번째 순서를 말한다. 괄호쌍이 맞아떨어지는 게 계속 이어붙는다면 결국 더 분리가 가능하기 때문이다.

예를 들어 "))(("가 있으면 균형잡힌 괄호 문자열이긴 하지만 "()"와 "()"로 2개의 균형잡힌 괄호 문자열로 분리가 된다. 즉, 더 이상 분리가 못하는 최소를 찾아야 한다.

"더 이상 분리할 수 없는 균형잡힌 괄호 문자열"로 만들어야 한다는 조건은, 주어진 문자열을 더 이상 쪼갤 수 없는 가장 짧은 단위의 균형잡힌 괄호 문자열로 만드는 것을 의미한다. 가장 처음으로 괄호의 짝이 맞아떨어지는 최소 길이의 균형잡힌 괄호 문자열을 찾는 것이며, 이렇게 분리한 문자열 u는 더 이상 더 짧은 균형잡힌 괄호 문자열로 분리되지 않는다.

// 예시: "(())()" 분석
// 인덱스별 괄호 개수 체크
// 0: '(' -> 왼쪽=1, 오른쪽=0
// 1: '(' -> 왼쪽=2, 오른쪽=0
// 2: ')' -> 왼쪽=2, 오른쪽=1
// 3: ')' -> 왼쪽=2, 오른쪽=2 ✅ 첫 번째 균형!
// 여기서 분리: u="(())", v="()"

구현 코드

// 올바른 괄호 문자열 체크
function check(s) {
  const stack = [];

  for (let char of s) {
    if (char === "(") {
      stack.push(char);
    } else if (char === ")") {
      if (stack.length === 0) {
        return false; // 닫는 괄호가 더 많은 경우
      }
      stack.pop();
    }
  }

  return stack.length === 0; // 모든 괄호가 매달되었는지 확인
}

// 균형잡힌 괄호 문자열을 u, v로 분리
function sepa(str) {
  let left = 0;
  let right = 0;
  let okidx = 0;

  for (let i = 0; i < str.length; i++) {
    if (str[i] === "(") left++;
    else if (str[i] === ")") right++;

    // 첫 번째 규형점에서 분리
    if (left === right) {
      okidx = i;
      break; // 첫 번째 균형만 찾고 종료
    }
  }
  return okidx;
}

// 메인 솔루션 함수
function solution(p) {
  if (!p.length) return "";

  let okidx = sepa(p);
  let u = p.slice(0, okidx + 1);
  let v = p.slice(okidx + 1);

  // u가 올바른 괄호 문자열인 경우
  if (check(u)) {
    return u + solution(v);
  }

  // u가 올바르지 않은 경우 (4단계)
  else {
    let result = "(" + solution(v) + ")";
    result += u
      .slice(1, -1)
      .split("")
      .map((el) => (el === "(" ? ")" : "("))
      .join("");
    return result;
  }
}

테스트 케이스

// 입력: "()))((()"
// 기댓값: "()(())()"

console.log(solution("()))((()")); // "()(())()"
console.log(solution("(()())()")); // "(()())()"
console.log(solution(")(")); // "()"

핵심 포인트

1. 분리 로직의 중요성

• 첫 번째 균형점에서 분리해야 재귀가 가능하다.
• 마지막 균형점을 선택하면 재귀 분해가 불가능하다.

2. 재귀적 사고

• 큰 문제를 작은 문제로 분해한다.
• 각 부분을 독립적으로 처리한 후 결합한다.

3. 스택 활용

• 괄호 매칭은 전형적인 스택 문제다.
• 시간복잡도: O(N), 공간복잡도: O(N)

마무리

이 문제는 알고리즘의 부분문제 분할(divide and conquer) 원리를 잘 보여주는 문제다. 특히 "더 이상 분리할 수 없는" 조건을 올바르게 해석하는 것이 핵심이었다.

한 줄 요약: 첫 번째로 괄호 개수가 같아지는 지점에서 분리하여 재귀적으로 처리하는 문제다.