[프로그래머스] 괄호 변환 (2020 KAKAO Blind Recruitment)

문제 링크

programmers.co.kr/learn/courses/30/lessons/60058

코딩테스트 연습 - 괄호 변환

 

풀이

문제에서 친절하게 해결 방법을 설명해줍니다.

 

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, 2, 3, 4] 과정을 반복하는데, 3, 4-2 단계에서 다시 1번으로 돌아가라고 합니다. 재귀 함수로 짜면 될 듯하네요.

 

좀 애매한 2단계만 해석해봅시다.

두 "균형 잡힌 괄호 문자열"로 $u$, $v$로 분리 → 따로 언급은 안됐지만 $u$는 분리된 왼쪽, $v$는 오른쪽 문자열이어야 합니다.

$u$는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없음 → $w$의 처음부터 시작되는 가장 작은 길이의 "균형잡힌 괄호 문자열"을 찾아 $u$로 두면 됩니다.

 

이후 문제에서 설명한 대로 구현하시면 됩니다.

자세한 내용은 코드를 참고해주세요.

정답 코드

class Stack{
  constructor(){
    this.stack = [];
  }
  push(x){
    this.stack.push(x);
  }
  pop(){
    this.stack.pop();
  }
  empty(){
    return this.stack.length === 0;
  }
  top(){
    return this.stack[this.stack.length-1];
  }
}
const foo = s => {
  if(s === '') return '';
  let open = 0, close = 0;
  let u ='', v='';
  for(let i=0; i<s.length; i++){
    if(s[i] === '(') open++;
    else close++;
    
    if(open === close) {
      u = s.substr(0, i+1);
      v = s.substr(i+1);
      break;
    }
  }
  if(isValid(u)) return u + foo(v);
  else return '('+foo(v)+')'+ reverseParens(u.substring(1, u.length-1));
}
const isValid = s => {
  const st = new Stack();
  s.split('').forEach(v => {
    if(!st.empty() && st.top() === '(' && v === ')'){
      st.pop();
    } else {
      st.push(v);
    }
  })

  return st.empty();
}
const reverseParens = s => {
  return s.split('').map(v=>v==='('?')':'(').join('');
}
function solution(p) {
  return foo(p);
}