[Leetcode] 오늘의 문제 - 241. Different Ways to Add Parentheses

문제

241. Different Ways to Add Parentheses

 

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 104.

 

 

키워드

Math
String
Dynamic Programming
Recursion
Memoization

 

 

내 첫번째 접근

• split을 활용한 숫자와 연산자(operator)를 배열로 분리
• 괄호를 어떻게 넣을까에 대한 고민 => 괄호에 집중.. 스택? 큐? 리스트? 자료구조 고민..

 

재귀적으로 문자열 처리하기 알고리즘

1. 입력받은 "전체 문자열"을 처리한다.

2. 재귀를 호출해 연산자를 기준으로 두 부분(왼쪽, 오른쪽)으로 나눈다.

3. 숫자만 남을 때까지 왼쪽, 오른쪽 각각 재귀를 호출한다.

4. 한자리 수 또는 두자리 수 숫자가 나오면 해당 숫자를 리턴한다.

5. 모든 경우의 수를 조합한다.

 

 

내가 빠진 늪

괄호에 집착해서 계산 결과를 리턴하면 되는데 괄호를 포함한 문자열을 만드려고 계속 고민했다. 

 

 

코드

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> diffWaysToCompute(String expression) {
        int n = expression.length();
        
        return recur(expression, 0, n-1);
    }

    public List<Integer> recur(String exp, int start, int end) {
        List<Integer> res = new ArrayList<>();	//재귀적으로 계산해 가능한 모든 결과를 넣는 자료구조
		
        if (start == end) {	//한자리 수 숫자인 경우
            int num = exp.charAt(start)-'0';    //유니코드를 활용해 문자를 숫자로 계산
            res.add(num);
            return res;
        } 
        if (end-start == 1 && Character.isDigit(exp.charAt(start))) {	//두 자리수 숫자인 경우
            int num = Integer.parseInt(exp.substring(start, end+1));
            res.add(num); 
            return res;
        }

        for (int i=start; i<=end; i++) {
            if (Character.isDigit(exp.charAt(i))) {
                continue;
            }
            //연산자(operator)
            char op = exp.charAt(i);
            //연산자를 기준으로 왼쪽, 오른쪽으로 나누어 재귀 호출
            List<Integer> left = recur(exp, start, i-1);
            List<Integer> right = recur(exp, i+1, end);
            
            //모든 경우의 수 조합
            for (int l : left) {
                for (int r : right) {
                    if (op == '*') {
                        res.add(l*r);
                    } else if (op == '+') {
                        res.add(l+r);
                    } else if (op == '-') {
                        res.add(l-r);
                    }
                }
            }
        }
        return res;
    }
}

 

 

Git

https://github.com/dev-jinius/Algorithm-Practice/tree/main/LeetCode/0241-different-ways-to-add-parentheses

Algorithm-Practice/LeetCode/0241-different-ways-to-add-parentheses at main · dev-jinius/Algorithm-Practice