[LeetCode] 394. Decode String 풀이 (javascript)

 

https://leetcode.com/problems/decode-string/description/?envType=study-plan-v2&envId=leetcode-75

 

간만에 올리는 알고리즘 포스팅

 

이번 문제는 leetcode의 394. Decode String 이다.

 

문제를 보자마자 기존에 접했던 괄호 채우기 stack 유형을 떠올렸다. 그런데 디테일한 로직을 짜려고 하니 머리가 너무 아팠다. 공간 지각 능력이 좀 부족해서

 

이런 문제를 풀때는 시물레이션을 돌리면서 차근 차근 로직을 세워 푸는것이 좋다.

 

 

로직을 세워 보자!

 

우선 for loop으로 문자열 s를 순회해 주자. 순회 시, 문자열 s의 character 마다 분기처리를 해주어야 한다.

 

1. digit은 괄호 [] 안에 들어갈 문자열의 반복 횟수 이다. digit은 한자릿수 이상이 될 수 있기 때문에, numCur 이라는 문자열에 저장해 둔다.

 

2. alphabet 을 만나면 문자열을 계속해서 생성해 주자! 이는 strCur이라는 문자열에 저장해 둔다.

 

3. 괄호(bracket) 의 시작 ' [ ' 을 만나면 지금 까지 저장해둔  numCur 와 strCur을 각각 numStack 과 outOfBracket 이라는 stack에 저장해 둔다.

numStack 은 괄호 바로 밖의 반복횟수 를 저장한것이며, outOfBracket은 괄호 바로 밖의 문자열을 저장한 것이다!

 

4. 괄호(bracket) 의 끝 ' ] ' 을 만나면 현재 문자열을

 

괄호 시작 직전 문자열 + numStack 에서 문자열의 반복횟수만큼 반복한 현재 문자열

=> outOfBracket.pop() + strCur.repeat(numStack.pop()

 

로 설정해 준다. 이는 괄호를 포함한 문자열 반복 수식을 하나 벗겨 낸것이며, 이를 반복해 반복 수식을 전부 처리할 수 있게 된다.

 

소스 코드

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function(s) {
    // num 값
    const numStack = []
    // bracket 바깥
    const outOfBracket = []
    
    let strCur = ""
    let numCur = ""
    for(let i=0; i<s.length; i++) {
        if('0' <= s[i] && s[i] <='9') {
           numCur = numCur + s[i]
        } else if('a' <= s[i] && s[i] <='z') {
            strCur = strCur + s[i]
        } else if(s[i] === '[') {
            outOfBracket.push(strCur)
            numStack.push(+numCur)
            numCur = ""
            strCur = ""
        } else {
            strCur = outOfBracket.pop() + strCur.repeat(numStack.pop()) 
        }
    }

    return strCur
};