재귀 함수 3부 (실제 코딩 테스트)

(코딩테스트 출처:

https://school.programmers.co.kr/learn/courses/30/lessons/60058?language=javascript)

 

처음 문제를 봤을때 문제를 이해하기부터 조차 힘들었다. 

문제를 요약하자면 괄호열기 '(' 와 괄호닫기 ')'의 쌍이 맞는 괄호들을 입력받으면 일정한 조건들에 충족하는 괄호로 재정립하는 문제이다.

 

그 조건들이란

1. 입력된 괄호들의 첫번째 문자열부터 추적하여 괄호의 쌍이 맞아 떨어지는 지점을 찾을것
2. 쌍이 맞아떨어지면 그 부분만 잘라내어 문자열을 체크후, 괄호닫힘으로 시작을 한다면 괄호열림으로 시작하도록 문자열 반전을 주어 재배치할것
3. 위의 과정들을 실행후 남은 부분들이 발생할경우 나머지 부분을 이용하여 위의 과정을 반복할것, 남은 부분이 없을수도 있음, 예를 들면 입력값이 한쌍의 괄호일경우 "()" 혹은 ")(" 와 "))((" 같이 같은 괄호가 반복적으로 올경우

위를 통해서 랜덤한 쌍의 랜덤한 배치의 괄호를 입력받더라도 조건에 맞게 정리가된 문자열을 출력하면 되는것이다.

전체코드

const fn = (p) => {
  if (!p) {
    return p;
  }
  
  
  const balance = (input, scales = null, count = 0, u = "", v = "") => {
    if (scales === 0) {
      return { u, v };
    }
    if (input[0] === "(") {
      scales++;
    } else {
      scales--;
    }
    u = u + input.slice(0, count + 1);
    v = input.slice(count + 1);
    return balance(input.slice(1), scales, count++, u, v);
  };


  const reverse = (input, result = "") => {
    if (!input) {
      return result;
    }
    result = result + input.slice(input.length - 1);
    return reverse(input.slice(0, -1), result);
  };


  const reBalance = (input, result = "") => {
    if (input.u[0] === "(" && !input.v) {
      result = result + input.u;
      return result;
    } else if (input.u[0] === ")" && !input.v) {
      return reverse(input.u);
    }
    if (input.u[0] === "(") {
      result = result + input.u;
    }
    const secondSubResult = balance(input.v);
    if (secondSubResult.u[0] === ")") {
      const reversedInput = reverse(secondSubResult.u);
      result = result + reversedInput;
    }
    return reBalance(secondSubResult, result);
  };


  const subResult = balance(p);

  const finalResult = reBalance(subResult);
  return finalResult;
};
fn(")(())(())(()")

 일단 위의 조건들을 반복문을 사용하지않고 오로지 꼬리재귀만을 사용해서 만들었다.

코드를 크게 3단계로 나눌수 있는데

1. balance() 함수로 입력값을 균형잡힌 문자열 즉, 완벽한쌍을 이루는 문자열로  잘라내기
2. reverse() 함수로 잘라내진 함수가 올바른 괄호 문자열이 아닐경우 (괄호닫힘으로 시작하는경우) 문자열을 뒤집어 올바른 괄호 문자열로 재정립하기
3. rebalance() 함수로 위의 단계이후 나머지값이 있다면 위의 단계를 반복하여 실행

이렇게 3단계로 나누어 코드를 짯다.

 

balance()

  const balance = (input, scales = null, count = 1, u = "", v = "") => {
    if (scales === 0) {
      return { u, v };
    }
    if (input[0] === "(") {
      scales++;
    } else {
      scales--;
    }
    u = u + input.slice(0, count);
    v = input.slice(count);
    return balance(input.slice(1), scales, count++, u, v);
  };

첫문자열부터 시작하여 완벽한 쌍을 찾아내기위한 꼬리재귀 함수로 인자로는 

1. input, 처음 주어지는 문자열 입력값
2. scales,  받은 입력값을 순차적으로 스캔후 그 값이 괄호열기 '(' 일 경우 +1, 괄호닫기 ')' 일 경우 -1이 주어지며 0이 됫을시 균형잡힌 괄호 문자열로 간주를 하고 매개변수 u 에 할당, 스캔이 안된 나머지 뒤의 부분들은 v에 할당
3. count, 반복수를 저장하며 input.slice(count)와 같이 이용해주어 문자열의 원하는 위치를 잘라내는데 사용
4. u, 처음 탐색된 균형잡힌 괄호 문자열을 등록
5. v, u값이 정립이 되고 나머지값이 있다면 나머지값을 등록

 

base case로는 scales가 0이되는때 즉 처음으로 균형잡힌 괄호 문자열을  찾아냈을때 등록된 u와 v를 반환하도록 하였다.

 

recursive case로는 먼저 입력값의 첫번째 문자열을 탐색하여 괄호열기 혹은 괄호닫기 인지 판단후 scales를 +1 혹은 -1 해준뒤 u값과 값을 저장해준다.

    u = u + input.slice(0, count);
    v = input.slice(count);

위와 같이 u와 v의 저장 형식이 다른이유는 u값은 함수가 반복됨에 따라 첫번째 문자열만 잘라내어 등록이 되면 되지만 v의 경우 균형잡힌 괄호 문자열이 어디까지인지 알수가 없으므로 함수가 반복될때마다 리셋을 시켜주었다.

 

이후 탐색이 완료된 첫번째 문자열을 제거한후 함수를 다시실행하여 첫번째 균형잡힌 괄호 문자열을 구할수 있었다. 

 

reverse()

이 함수의 경우 일반적인 문자열 반전 꼬리함수로 이전의 포스트에 기재되어있으므로 설명 생략

 

rebalance()

이함수는 처음 balance() 함수를 통해 u값을 결과값으로 저장하고 만약 v값이 있다면 v값을 가지고 balance()함수를 이용하여 다시 u와 v값으로 재정립, 그후 또다시 u값은 기존의 결과값과 합처서 저장, v값이 존재할경우 반복하여 u와 v값으로 재정립하여 v값이 남지 않을때까지 실행 후 결과를 도출하는 함수이다.

  const reBalance = (input, result = "") => {
    if (input.u[0] === "(" && !input.v) {
      result = result + input.u;
      return result;
    } else if (input.u[0] === ")" && !input.v) {
      result = result + reverse(input.u);
      return result;
    }
       
    if (input.u[0] === "(") {
      result = result + input.u;
    }
    if (input.u[0] === ")") {
      const reversedInput = reverse(input.u);
      result = result + reversedInput;
    }
    
    const secondSubResult = balance(input.v);
    
    return reBalance(secondSubResult, result);
  };

첫번째 인자인 input의 경우 balance()함수의 리턴값이므로 객체 {u, v}로 되어있다. result의 경우 u값을 계속하여 저장해준뒤 base case에 나온것처럼 input.v가 없을경우 함수의 반복을 중단하고 result값을 반환한다.

 

이경우 base case가 2가지인데 첫번째는 올바른 괄호 문자열일경우 즉 괄호열기 '('로 시작되는경우 u값을 result에 바로저장해준뒤 리턴해주고 두번째의 경우인 올바르지 못한 괄호 문자열일 경우 즉 괄호닫기 ')'로 시작되는경우 reverse()함수를 이용하여 문자열을 뒤집어주고 올바른 괄호문자열로 만들어 리턴해주었다.

 

recursive case도 두가지경우 즉 u값이 올바른 괄호 문자열일경우와 아닐경우로 나눠 주어야 했으며 올바른 괄호 문자열일경우 기존의 result값과 더하여 u값을 그대로 저장, 올바르지 않을경우 u값을 reverse()함수로 반전을 준뒤 result에 저장

 

그이후 v값을 이용하여 balance()를 이용하여 또다시 u와 v값을 나눠준뒤 reBalance함수 재실행하여 어떤 문자열이 오더라도 잘 정열된 괄호 문자열을 받을수있게 된다.

 

마무리

처음 코드를 설계하는 과정부터 쉽지 않았다. 

기존에 사용해오던 반복문으로 코드를 짜게된다면 일의 순서대로 처리하면 그만이었지만 재귀를 사용하다보니 어디서부터 시작해야될지 몰랐다. 

 

장장 3시간이 걸려 코드를 완성시키면서 들었던 생각을 적어보겠다.

 

첫번째로, 문제의 접근을 달리해야됬다. 처음 어떻게 시작해야될지 감도 잡지 못했었다. 그러다 문득 재귀 '함수'이므로 부분적으로 함수를 만들어 접근을 시작해보자 생각했더니 조금씩 접근이 가능했다. 

그렇게 문제를 부분적으로 balance(), reverse(), rebalance()함수들로 나눈뒤 접근하였더니 그이후의 코드들은 물흐르듯이 작성이 되어 기분좋은 경험을 했다.

 

두번째로, 반복문의 경우 문제의 순서대로 코드를 작성하면 그만이었지만 재귀함수의 경우 문제의 마지막 부분부터 접근 즉 base case를 어떻게 구현할것인지를 먼저 구상을 끝내야 됫다. 예를 들자면 도미노를 만든다고 가정했을때 반복문은 도미노의 처음부터 하나씩 차례로 쌓으면 되지만 재귀의 경우 도미노의 전체적인 흐름을 구상한뒤 섹션을 나누고 각각의 섹션의 마지막 도미노 부터 쌓는 느낌이었다. 

 

세번째로, 이상하게 개인적으로 일반재귀함수보다 꼬리재귀함수가 더 접근하기가 쉬웠다. 개인의 사고방식에 따라 느끼는 바가 다른것 같으며 그 사고방식의 유연성이 문제를 더 쉽게 해결하는데 중요한 포인트인것 같다.

 

이를통해 느낄수 있었던건 문제를 바라보는 시각의 중요성이다. 여러가지 방향에서 문제를 바라볼수록 더많은 해답 혹은 더 효율적인 해답이 나올수 있는것 같다.