[LeetCode] 241. Different Ways to Add Parentheses

https://leetcode.com/problems/different-ways-to-add-parentheses/description/?envType=daily-question&envId=2024-09-19

leetcode - Different Ways to Add Parentheses

문제 유형 : 문자열 처리, 재귀, 다이나믹 프로그래밍, 카탈란 수

문제 난이도 : Medium

 

문제

Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.

The test cases are generated such that the output values fit in a 32-bit integer and the number of different results does not exceed 10^4.

 

숫자와 연산자로 이루어진 문자열 수식이 주어진다. 연산들 사이에 모든 가능한 괄호쌍을 각각 적용시킨 연산의 값들을 배열에 담아서 반환하시오.

순서는 상관없습니다.

개수가 10^4개까지는 안되도록 보장되어있습니다.

 

각 오퍼랜드는 0~99사이의 정수입니다.

 

풀이

이 문제는 카탈란수와 연관이 있다.

https://riveroverflow.tistory.com/entry/%EC%B9%B4%ED%83%88%EB%9E%80-%EC%88%98%EB%9E%80

카탈란 수란?

 

 

연산자들에게 괄호로 우선순위를 주고 연산순서를 바꿔가면서 여러 가능한 값들을 구하는 것은, 이진 탐색에서의 중위순회라고 생각할 수 있겠다.

연산자를 현재 서브트리의 루트, 왼쪽, 오른쪽 오퍼랜드를 각각 왼쪽, 오른쪽 서브트리라고 볼 수 있다.

 

 

이러한 트리-라이크의 형태를 만들기 위해, 모든 연산자 및 피연산자를 한 노드에 저장시킬 것이다.

+를 101, -를 102, *를 103이라고 매핑해서 배열에 수식을 파싱해서 정수 배열에 저장하자.

이러면 리프노드들을 순차적으로 배열에 담은 셈이 된다.

 

우리는 dp[left][right] = 왼쪽에서 left번째 노드부터 오른쪽에서 right번째 노드까지 연산한 값들의 가능한 모든 조합들

이라고 저장할 것이다.

 

left는 0에서 시작하고, right는 n-1(=수식에서의 피연산자 및 연산자의 수 총합)에서 시작한다.

 

재귀로 dp테이블을 채울 수 있다:

  우선, left가 right보다 작다면, 유효하지 않은 순회이므로 빠져나온다.

  left == right라면, 만약 nums[left]가 피연산자라면, {nums[left]}를 반환한다.(오퍼랜드 1개)

  만약 dp[left][right]가 있다면, 그 dp값을 반환한다.

  

  left ~ right에 대해 다음을 반복한다:

    만약 현재 요소가 오퍼랜드라면, 건너뛴다.

    현재 요소가 연산자라면, left부터 현재 요소 전까지의 재귀 호출 값을, 즉 left요소부터 이전 요소까지 연산된 모든 경우들을 operandL에 저장한다.

    그리고, 현재 요소 이후부터 right까지 재귀 호출 값을, 즉 현재 요소 이후부터 right까지의 연산된 모든 경우들을 operandR에 저장한다.

    현재 연산자에 대해서, operandL과 operandR에서 각각 하나씩 골라서 만들어낼 수 있는 모든 연산을 만들어서 dp[left][right]에 저장하고 그 값을 반환한다.

 

main이 되는 함수에서는 expression을 파싱한뒤, 첫 재귀호출(left : 0, right : n-1)을 한 값을 반환하면 된다.

 

코드

C++

class Solution {
private:
    vector<int> dp[20][20];
    vector<int> convert(string &expression) {
        vector<int> res;
        int x = 0;
        int size = expression.size();
        for(int i = 0; i < size; i++) {
            char c = expression[i];
            switch(c) {
                case '+': res.push_back(101); break;
                case '-': res.push_back(102); break;
                case '*': res.push_back(103); break;
                default: {
                    x = 10 * x + c - '0';
                    if (i == size-1 || !isdigit(expression[i+1])) {
                        res.push_back(x);
                        x = 0;
                    }
                }
            }
        }

        return res;
    }

    vector<int> solve(int left, int right, vector<int> &nums) {
        if(left > right) return {};
        if(left == right){ 
            if(nums[left] >= 101) return {};
            return {nums[left]};
        }
        if(dp[left][right].size() > 0) return dp[left][right];

        vector<int> res;
        for(int i = left; i <= right; i++) {
            if(nums[i] < 100) continue;
            auto operandL = solve(left, i-1, nums);
            auto operandR = solve(i+1, right, nums);
            for(int l : operandL) {
                for(int r : operandR) {
                    int x = 0;
                    switch(nums[i]) {
                        case 101: res.push_back(l + r); break;
                        case 102: res.push_back(l - r); break;
                        case 103: res.push_back(l * r); break;
                    }
                }
            }
        }
        return dp[left][right] = res;
        
    }
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> nums = convert(expression);
        int n = nums.size();
        return solve(0, n-1, nums);
    }
};