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

 

function solution(p) {
  let left = 0;
  let right = 0;
  let answer = "";

  if (p === "") return "";

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

    if (left === right) {
      if (check(p.slice(0, i + 1))) {
        answer = p.slice(0, i + 1) + solution(p.slice(i + 1));
        return answer;
      } else {
        answer = "(" + solution(p.slice(i + 1)) + ")";
        for (let j = 1; j < i; j++) {
          if (p[j] === "(") answer += ")";
          if (p[j] === ")") answer += "(";
        }
        return answer;
      }
    }
  }
}
function check(p) {
  let stack = [];
  for (let i = 0; i < p.length; i++) {
    if (p[i] === "(") stack.push("(");
    else {
      if (stack.length === 0) return false;
      stack.pop();
    }
  }
  return true;
}

처리 순서

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. 생성된 문자열을 반환합니다.

1. if문으로 p가 빈 문자일경우 빈문자열을 리턴한다.

2. 우선 들어온 문자를 균형잡힌 괄호문자열과 나머지 v로 분리시킨다. 균형잡힌 괄호문자열이란 "("와 ")"의 갯수가 동일해야한다. 그래서 먼저 p의 length만큼 for문을 돌리기 시작하고 하나씩 검사하며 left는 "(" right는 ")" 일 때마다 카운트를 올린다.

3. 만약 균형잡힌 괄호 문자열이 탄생하려면 left와 right가 같아야하고 같을 시 올바른 괄호문자열인지 아닌지 검사하게 된다.

4. 올바른 괄호 문자열은 check라는 함수로 검사하며 파라미터로 검사할 값을 넣을시 ( 와 ) 순으로 들어가야 올바르다고 판단할 수 있으로 빈 stack에 하나씩 쌓으며 ) 일시는 안에 쌓인것을 pop하여 뺀다. 아직 쌓아볼 문자열이 남았는데도 뺄 ( 이 없다면 올바르지 않은 괄호 문자열 이라고 할 수있다.

5. 올바른 괄호 문자열이라고 판단된다.면 i+1까지 (u) 에다가 재귀함수를 통해 i+1부터를 다시 넣어 수행한뒤 붙여서 answer로 반환한다.

6. 만약 올바른 괄호 문자열이 아니라면 ( 와 v에 대한 재귀를 한뒤 ) 를 붙인다.

7. 첫번째와 마지막을 제외한 문자열을 뒤집어서 answer에 ++ 한다.