[알고리즘] LeetCode Decode String JS

개요

암호화된 하나의 문자열이 주어지는데 이걸 해독해서 return하면 되는 문제이다.

 

복호화하는 방식은 다음과 같다.

 

2[ac] => acac , 3[cd]2[ff] => cdcdcdffff

 

숫자[문자] 규칙을 가지며 [ ] 안에 있는 문자는 숫자만큼 반복해서 꺼낸다. 이렇게 모든 문자를 원본 문자열로 돌리면 된다

Backspace String Compare - LeetCode

 

풀이

우선 스택으로 풀면 될거같다는 생각을 했다.

 

우선 닫는 괄호를 만날 때 까지 계속해서 stack에 넣는다.

닫는 괄호를 만난다면 여는 괄호를 만날 때 까지 모든 문자열을 꺼낸다.

여는 괄호( [ ) 뒤는 무조건 숫자가 나오기 때문에 숫자만큼 꺼낸 문자열을 .repeat()라는 내장함수를 이용해서 반복해주었다.

 

테스트 케이스는 넘어가고 실제 제출했을 때는 반복되는 숫자때문에 문제가 있었다

 

한 자리 숫자만 나오면 문제가 없는데 10의 자리까지 나오게 되면 생기는 문제였고 문자열 문제를 풀면서 자주 놓치는 부분이었다.

 

isNaN이라는 메소드를 통해 스택에서 더 꺼내 해결하였다

 

/**
 * @param {string} s
 * @return {string}
 *
 * s가 암호화된 문자열로 주어진다
 *
 * 숫자와 문자로 이루어져있는데 숫자만큼 괄호 안 문자를 반복한다
 *
 * 최종적으로 모두 풀어내면 된다
 *
 * .repeat라는 함수가 있는데 문자열 갯수만큼 반복해준다
 * [를 만나면 마지막 문자가 숫자라는 뜻
 * ]를 만나면 문자가 끝이라는 뜻
 *
 * ]를 만나서 다 뻈는데 스택이 남아있다면 스택에 완성 문자열을 다시 넣어준다.
 *
 * 숫자의 대한 문자처리가 필요하다 한 자릿수 밖에 처리가 안됨.
 */
const popString = (stack) => {
  let tmp = "";

  while (stack[stack.length - 1] !== "[") {
    tmp = stack.pop() + tmp;
  }
  stack.pop(); // [ 만나서 종료

  return tmp;
};

const parseNumber = (stack) => {
  let number = "";
  let current = stack.pop();

  // NaN일때 true를 뱉는다 따라서 NaN이 안나올떄까지 더해준다
  while (!Number.isNaN(Number(current))) {
    number = current + number;
    current = stack.pop();
  }

  stack.push(current);

  return Number(number);
};

var decodeString = function (s) {
  let answer = "";

  const stack = [];

  for (const char of s) {
    if (char !== "]") stack.push(char);
    else {
      // ]를 만났을 떄
      const tmp = popString(stack);
      const number = parseNumber(stack); // 숫자가 나옴

      const decode = tmp.repeat(number);
      stack.push(decode);
    }
  }

  return stack.join("");
};