스택의 자료구조로 함수 호출을 모사하기

안녕하세요, 저는 이직 막바지 작업에 한창입니다.

이 포스트는 코딩 테스트 오답노트입니다, 성적이 좋은 분들은 오답노트를 꼭 쓰더군요.

 

문제의 출처는 리트코드 394번, "Decode String" 문제입니다.

Decode String - LeetCode

 

문제를 한 번 볼까요? `k[encoded_string]`처럼 생긴 압축 규칙이 있습니다. encoded_string은 알파벳 소문자로 제한되고, 압축 규칙 내의 압축 문자열은 또 다른 압축 규칙을 포함할 수도 있습니다. k는 최소 1에서 최대 300의 정수입니다.

 

우선 한 번 풀어보고,

function decodeString(s) {
  let result = "";
  let iteration = 0;
  const stack = [];
  for (const char of s) {
    if (Number.isSafeInteger(Number(char))) {
      iteration && (iteration *= 10);
      iteration += Number(char);
    } else if (char === "[") {
      stack.push({
        iteration,
        value: ""
      });
      iteration = 0;
    } else if (char === "]") {
      const {iteration, value} = stack.pop();
      const invoked = value.repeat(iteration);
      if (stack.length) {
        const lastNode = stack[stack.length - 1];
        lastNode.value += invoked;
      } else {
        result += invoked;
      }
    } else if (stack.length) {
      const lastNode = stack[stack.length - 1];
      lastNode.value += char;
    } else {
      result += char;
    }
  }
  return result;
}

이것을 아래와 같이 서브프로시져로 리팩터링하도록 합니다.

function decodeString(s) {
  const stack = [];
  const context = {
    iteration: 0,
    result: "",
    stack
  };
  for (const char of s) {
    if (Number.isSafeInteger(Number(char))) {
      parseNumber.call(context, char);
    } else if (char === "[") {
      pushStack.call(context, char);
    } else if (char === "]") {
      popStack.call(context, char);
    } else {
      appendValue.call(context, char);
    }
  }
  return context.result;
}

function parseNumber(char) {
  this.iteration && (this.iteration *= 10);
  this.iteration += Number(char);
}

function pushStack(char) {
  const {iteration, stack} = this;
  stack.push({iteration, value: ""});
  this.iteration = 0;
}

function popStack(char) {
  const {iteration, value} = this.stack.pop();
  const invoked = value.repeat(iteration);
  appendValue.call(this, invoked);
}

function appendValue(str) {
  const {stack} = this;
  if (stack.length) {
    const lastNode = stack[stack.length - 1];
    lastNode.value += str;  
  } else {
    this.result += str;
  }
}

압축 규칙을 만나면, 그러니까 "[" 문자열을 만나면 스택을 채워넣고, 내부의 문자열을 해당 스택 노드의 value 속성에 덧붙입니다.

 

"["를 만나기 전의 숫자는, 그 스택 노드의 반복 횟수가 되니까 전체 함수의 컨텍스트 내에서 그 숫자를 파싱합니다. 저는 높은 자리부터 세고, 숫자가 끝날 때까지 이전의 수를 10씩 곱하는 방식을 택했어요. 그러므로 맨 처음에 이야기했던 스택을 채워넣는 서브프로시져 pushStack 끝 부분에서 컨텍스트의 iteration 변수를 0으로 초기화하여야 합니다.

 

스택 노드의 레이아웃은 아래와 같습니다.

interface Node {
  iteration: number;
  value: string;
}

한 번 스택이 채워지면, 그러니까 현재 압축 규칙을 파싱 중인 상태state `context.stack.length !== 0`이라면 마지막 노드의 값을 계속 덧붙입니다. 그러다가 다른 압축 규칙을 만나면 아까와 같은 순서(반복 횟수를 먼저 파싱하고 노드를 삽입)로 새로운 노드를 스택에 추가합니다.

 

"]"를 만나면 스택을 털 때가 된 것입니다. 마지막 노드를 pop하고, value를 iteration만큼 반복하여 디코딩된 값을 구합니다. String#decode 메소드를 사용하였어요. 아직 스택 내에 다른 노드가 남아있으면, 마지막 노드의 value에 디코딩된 값을 덧붙입니다. 스택이 비어있다면 메인 함수의 컨텍스트 result에 값을 덧붙입니다.

 

이상입니다, 문제없이 잘 동작하네요.

(문서의 끝)