[리트코드] Different Ways To Add Parentheses <Java>

문제

---

https://leetcode.com/problems/different-ways-to-add-parentheses/submissions/

Different Ways to Add Parentheses - LeetCode

 

수식으로 만들어 낼 수 있는 결과 값의 리스트를 리턴하면 되는 문제

 

풀이

---

완전탐색을 이용하여 문제를 푼다.

 

알고리즘 순서

1. 연산자를 만나면, 연산자 기준으로 왼쪽과 오른쪽을 나눠 재귀적으로 다시 함수에 넣어준다.
2. 왼쪽의 결과값과, 오른쪽의 결과 값을 현재의 연산자를 이용하여 모두 계산해준다.
3. 만약 결과 값 리스트가 없다면 숫자만 남은 것이므로 해당 식을 숫자화 시켜준다.

<전체코드>

import java.util.*;

class Solution {
    public List<Integer> diffWaysToCompute(String expression) {
        List<Integer> answer = new LinkedList<>();            
        for(int i = 0 ; i < expression.length() ; i++){            
            char c = expression.charAt(i);
            if(c == '-' || c == '+' || c == '*'){
                List<Integer> left = diffWaysToCompute(expression.substring(0, i));
                List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
                
                for(Integer l : left){
                    for(Integer r : right){
                        answer.add(calculator(l, r, c));
                    }
                }
            }
        }
        
        if(answer.isEmpty()){
            answer.add(Integer.parseInt(expression));
        }
        
        return answer;
    }
    
    public int calculator(int a, int b, char ex){
        
        if(ex == '-'){
            return a - b;
        }
        
        if(ex == '+'){
            return a + b;
        }
        
        if(ex == '*'){
            return a * b;
        }
        
        return 0;
    }
}