394. Decode String

💡 풀이

// O(N)
const decodeString = s => {
  let stack = [];
  let numStack = [];

  let num = 0;
  let str = '';

  for (let i = 0; i < s.length; i++) {
    // 여는 괄호가 나왔을 때 (stack과 numStack에 push할 때)
    if (s[i] === '[') {
      stack.push(str);
      numStack.push(num);
      str = '';
      num = 0;
      continue;
    }
    // 닫는 괄호가 나왔을 때 (str을 만들 때)
    else if (s[i] === ']') {
      str = stack.pop() + str.repeat(numStack.pop());
      continue;
    }
    // 숫자가 나왔을 때
    if (s[i] < 97 || s[i] > 122) num = num * 10 + Number(s[i]);
    // 알파벳이 나왔을 때
    else str += s[i];
  }
  return str;
};

📝 정리

역시 stack을 이용한 문제다. O(N)의 시간복잡도로 해결하였다. 해결 방안 자체는 많이 어렵지 않게 생각한 편이지만 그걸 코드로 구현하는 데에 매우 오래걸렸다..! (해결은 했는데 속도도 그리 빠르지는 않다.)

• 이전에 풀었던 문제와 비슷하게 두 개의 stack이 필요하다. stack과 numStack으로 선언하였다.

• 또한 숫자를 계산할 num과 (숫자가 10의 자리를 넘어가는 경우를 위해 ex: 42) 답이 될 str 변수를 선언해준다.

• 이후 반복문을 돌며 여는 괄호(='[')가 나왔을 때, stack 배열에 str을 저장하고, numStack 배열에는 num을 저장해준다. 이후 str과 num을 각각 ''와 0으로 다시 초기화 시켜주고, continue를 통해 아래 코드를 무시하고 다시 loop을 돌게 한다.

• 닫는 괄호(=])가 나왔을 때는 답이 될 str을 만들 때다. str를 numStack.pop()의 개수만큼 곱해주고(=repeat 메서드로), stack.pop()을 더해준다.

• 그리고 괄호가 아닌 숫자가 나왔을 때와 알파벳이 나왔을 때도 분기처리를 해줘야 하는데, 숫자가 나왔을 때는 숫자가 10의 자리를 넘어가는 경우가 있기 때문에 다음 코드와 같이

  num = num * 10 + Number(s[i]);

• num값을 업데이트한다.

• 알파벳이 나왔을 때는 str에 계속 합쳐주면 된다.

후기

이미 stack 문제를 계속 연습 중이어서, stack에 맞춰 생각을 해서 그런지 방법 또한 오래 걸리지 않게 생각을 한 문제였다. 문제는 그걸 코드로 구현하는데 정말 오래 걸렸다는 것인데.. 언젠가 500문제(??)정도 넘게 풀면 그때는 뭔가 구현에 속도가 붙으려나?

수정, 지적을 환영합니다!

문제 링크

https://leetcode.com/problems/decode-string/

LeetCode GitHub

https://github.com/tTab1204/LeetCode