괄호변경

YEONGHUN KO·2021년 12월 21일

ALGORITHMS - PRACTICE

목록 보기

43/50

1. 괄호변경

괄호가 주어진다. 그 괄호들이 짝은 맞는데 방향이 맞지 않는 경우가 대부분이다. 예를 들어, (()())() 는 올바른 괄호이다. 괄호의 방향들이 맞아떨어지기 때문이다. 하지만 (())())))((( 는 올바른 괄호가 아닌 단지 균형잡힌 괄호일 뿐이다.

따라서 위의 균형잡힌 괄호를 (())()()(()) 이런식으로 올바른 괄호로 바꾸는 프로그램을 만들어야 한다. 친절하게도 pseudo code가 적혀있다.

2. 접근방법

dfs를 써서 접근한다. 우선 괄호가 주어지면 올바른 괄호를 'u' 라고 하고 균형잡힌 괄호를 'v'라고 한다. 그래서 u / v로 나눈다. 나눠진 v에 올바른 괄호가 있다면 올바른 괄호를 u만 덜어내고 나머지를 재귀에 pass한다.

그럼 pseudo code를 자세히 보도록 하자.

pseudo code
1.입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
2.문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
3.문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
- 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
4.문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
- 4-1.빈 문자열에 첫 번째 문자로 '('를 붙입니다.
- 4-2.문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
- 4-3.')'를 다시 붙입니다.
- 4-4.u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
- 4-5.생성된 문자열을 반환합니다.

처음 이 로직을 읽었을때 무슨 말인지 한참을 살펴봐도 이해가 안되더이다. 코드를 적어보려고 했지만 실패해서 결국 답을 보고 테스트 케이스를 적용해보니 이해가 되었다. 2가지 solution을 살펴볼건데 첫번째는 알기 쉽게 풀어서쓴 산문이라고 한다면 두번째 solution은 깔끔하게 압축한 운문이라고 보면 된다.

우선 (())())))((( 가 pass되었다고 한 번 가정해보자.

2-1. solution1(산문)

function solution1(p) {
  let answer = "";
  let left = 0; // 현재 왼쪽 괄호 개수
  let right = 0; // 현재 오른쪽 괄호 개수
  let check = false; // '올바른 괄호' 인지 아닌지

  // 1. p가 빈문자일 경우 빈문자열 반환
  if (p.length == 0) return "";

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

    // 핵심개념 : 오른쪽 괄호가 왼쪽 괄호의 수를 넘으면 그때부터 '올바른 괄호' X
    if (right > left) check = true;

    // 2. 균형잡힌 u가 나와서 쪼갤 타이밍 (u,v)
    if (left == right) {
      // 4. '올바른 괄호' X
      if (check) {
        // ')))(((' 라고 하면 여기서 일단  () 를 만든다.
        // 4-1. 즉, 맨 앞, 맨 뒤 괄호를 빼서 ()를 만들어준다는 의미와 같다.
        answer += "(";
        // 4-2. 만약 ')))(((' 뒤에 더 있으면 남은것을 다시 재귀로 보내서 정리한다음 여기로 오게하기 위해서
        // 재귀를 사이에 넣음
        answer += solution1(p.slice(i + 1, p.length));
        answer += ")";

        // 4-4. 그리고 여기서 ))(( 를 (()) 로 바꾸어 주는 것이다.
        // j가 1부터 4까지 만 증가하는 것도 그러한 이유이다.
        // 그리고 마지막 return에서 () + (()) => ()(()) 를 해주는 것이다!

        // 첫번째, 마지막 문자 제거하고 나머지 반전 후 뒤에 붙이기
        for (let j = 0; j < i; j++) {
          if (p[j] === ")") answer += "(";
          if (p[j] === "(") answer += ")";
        }

        // 4-5. 생성된 문자열 반환
        return answer;
      }

      // 3. 만약 올바른 괄호면 올바른 괄호 까지만 잘라내고 나머지를 재귀에 넣어서 정제 한다음
      // 올바른 괄호랑 합치면 된다.
      // '올바른 괄호' O
    } else {
      answer += p.slice(0, i + 1);
      answer += solution1(p.slice(i + 1, p.length));
      return answer;
    }
  }
}

디버깅을 해보면은 알것이다 이 pseudo code가 얼마나 정교하고 아름다운지를 그리고 solution1이 얼마나 그것을 얼마나 쉽고 상세하게 표현하고 있는가를.

그러나 여기서 끝이 아니다 또 다른 아름다움을 가진 solution2를 만나보자.

2-2. solution2(운문)

// 4-4. u의 첫번째와 마지막 문자를 제거하고, 나머지 문자열을 뒤집어서 반환
function reverse(str) {
  return str
    .slice(1, str.length - 1)
    .map((c) => (c === ")" ? "(" : ")"))
    .split("")
    .join("");
}

function solution2(p) {
  if (p.length === 0) return "";

  let balance = 0;
  let pivot = 0;

  do {
    // 아하! do/while을 do를 먼저하는구나? 그리고 condition을 체크하는구나?
    // 그래서 최소 1번이상은 loop가 돌겠구나?
    // 2. u / v를 분리하는 과정
    balance += p[pivot++] === "(" ? 1 : -1;
  } while (balance !== 0);

  // 위에서 처럼 올바른 괄호인지 균형잡힌 괄호인지 구분한다음 4번으로 가지 않음
  // 바로 u / v로 나뉜다음 v는 재귀를 통해 정제되어 돌아와서 u랑 합쳐짐

  const u = p.slice(0, pivot);

  // 3. 문자열 v에 대해서는 다시 재귀를 수행해서 올바른 괄호로 변환함

  const v = solution2(p.slice(pivot, p.length));

  // 3-1. u라면은 v랑 바로 합쳐버림
  if (u[0] === "(") return u + v;
  // 4-1. v에 대해서는 앞뒤를 () 로 바꾸고 안쪽은 방향을 전환해서(reverse) 합친다음 반환 함
  else "(" + v + ")" + reverse(u);
}

solution2("()))((()");
solution2("(())())))(((");
solution2("(()())()");

//      p	        result
// "(()())()"	  "(()())()"
//    ")("	     "()"
// "()))((()"	  "()(())()"

// 이해했다. 더 깔끔하고 세련되었다. 진짜 세상은 넓고 고수분들은 많다!! 진짜 끊임없이 배우고 성장해서 너무너무너무너무 좋다
// 다 정리한다음 내혼자서 안보고 구현해보자!