Different Ways to Add Parentheses

Different Ways to Add Parentheses

문제 내용

숫자와 +,-,* 3개의 Operation으로 구성된 문장이 있다.

임의로 () <- 괄호를 만든다고 했을 때 나올 수 있는 모든 답을 구하시오.

중복 허용.

 

접근 방법

언듯 쉬워보이는 문제였는데, 

• 1 <= expression.length <= 20

이 제한 사항을 확인했을 때, 쉬운 방법으로 해결이 안된다는 것을 알았어야 했다.

즉 Operation은 최대 9개가 넘어 가지 않는다.

1+1+1+1+1+1+1+1+1+11

제한사항이 작다는 것을 봤을 때 NP문제라는 것을 알지 못했던 부분이 아쉽다.

아무튼 결국 전 검색이 필요하다.

그럼 모든 경우의 수를 확인하는 방법은 어떻게 해야할까?

괄호를 크게 잡았을 경우를 생각해 보자.

(1)+(1+1+1+1+1+1+1+1+11)

(1+1)+(1+1+1+1+1+1+1+11)

....

(1+1+1+1+1+1+1+1+1)+(11)

특정 Operation을 가운데 두고 양쪽의 결과를 처리하는 방식으로 생각 할 수있다.

이렇게 분리를 하면 가로안의 값은 다시 동일한 방식으로 계산이 가능하다.

(1+1+1+1+1+1+1+1+1)

((1)+(1+1+1+1+1+1+1+1))

.....

((1+1+1+1+1+1+1+1)+(1))

다시 한번더 괄호를 만들어 낼 수 있다.

(1+1+1+1+1+1+1+1)

((1)+(1+1+1+1+1+1+1))

....

((1+1+1+1+1+1+1)+(1))

이런 방식으로 괄호를 칠 수 있는 모든 경우의 수를 만들어 낼 수 있게 된다.

• Operation을 만나면 해당 Operation을 중심으로 양쪽을 나누어서 양쪽에서 올수 있는 모든 경우의 수를 합산한다.

그럼 코드로 해당 내용을 만들어 보자.

var diffWaysToCompute = function(expression) {
    
    let ans = new Array();
    
    for(let i = 0; i < expression.length; i++){
        let char = expression.charAt(i);
        
        if(char.indexOf('+-*')){
            let leftArr = diffWaysToCompute(expression.substring(0,i));
            let rightArr = diffWaysToCompute(expression.substring(i+1,expression.length));
            
            for(let l = 0; l < leftArr.length; l++){
                for(let r = 0; r < rightArr.length; r++){
                    if(char === '+'){
                        ans.push(leftArr[l] + rightArr[r]);
                    }
                    if(char === '-'){
                        ans.push(leftArr[l] - rightArr[r]);
                    }
                    if(char === '*'){
                        ans.push(leftArr[l] * rightArr[r]);
                    }
                }
            }
        }
    }
    
    if(ans.length === 0) ans.push(parseInt(expression));
    
    return ans;
    
};

위의 코드는 Time Complexity를 계산해 보면

Operation 숫자만큼 한번 계산하고,

다음 Operation에서 Operation 횟수 - 1회 만큼 다시 한번더 Search한다. 그리고 다음 dfs에서 한번더 -1회 만큼 Search한다. 해당 expression에 Operation이 없을 때까지 진행 한다.

즉 Operation 1회에 $ N^2 $ 만큼 깊이로 들어가고 for로 전체 순회를 한번더 하니까 

$$ O(N^3) $$

이 된다.

이 부분을 최적화 하기 위해서 DP를 사용해 보자.

Expression에서 나올 수 있는 결과값의 Set은 항상 고정 될 수 있음으로

한번 사용된 Expression을 Cache처리 하도록 하자.

예를 들자면

1 *2+3 은

$ (1 *2) +3 = 5 $ or $ 1 * (2+3) = 6 $ 두 개 인것은 불변이다.

이것을 Map에 저장해서 재활용 할 수 있게 만들자.

var diffWaysToCompute = function(expression, dp = new Map()) {
    if(dp.has(expression)) return dp.get(expression);
    
    let ans = new Array();
    
    for(let i = 0; i < expression.length; i++){
        let char = expression.charAt(i);
        
        if(char.indexOf('+-*')){
            let leftArr = diffWaysToCompute(expression.substring(0,i),dp);
            let rightArr = diffWaysToCompute(expression.substring(i+1,expression.length),dp);
            
            for(let l = 0; l < leftArr.length; l++){
                for(let r = 0; r < rightArr.length; r++){
                    if(char === '+'){
                        ans.push(leftArr[l] + rightArr[r]);
                    }
                    if(char === '-'){
                        ans.push(leftArr[l] - rightArr[r]);
                    }
                    if(char === '*'){
                        ans.push(leftArr[l] * rightArr[r]);
                    }
                }
            }
        }
    }
    
    if(ans.length === 0) ans.push(parseInt(expression));
    
    dp.set(expression, ans);
    
    return ans;
    
};

 

이렇게 하면 Operation만큼 1회 검색 후 양쪽 한번씩 검색하고 저장이 된 부분은 즉각 결과를 내놓음으로

$$ O(N^2) $$ 으로 충분하게 된다.

미디엄 문제인데... 전순환 문제는 꼭 hard를 푸는 느낌이다. 

아 혹시나 해서 위의 Time Complexity는 대략적인 것이고 정확한것은 하기 link의 

https://people.math.sc.edu/howard/Classes/554b/catalan.pdf

https://www.geeksforgeeks.org/program-nth-catalan-number/

내용을 확인해야 할 것 같은데 너무 복잡해서 Pass...