Problem: Finding Parentheses Arrangement that Minimizes Value
Algorithm problems play an important role in coding tests, and especially problems related to parentheses are often presented. In this article, we will address the challenge of finding the minimum value by considering all possible parentheses arrangements for a given expression. We will explain the theories and algorithms necessary to solve this problem in detail.
Problem Description
There is a string composed of given numbers and operators. This string can be calculated by placing parentheses in various ways. Our goal is to find the minimum value that can be obtained by placing parentheses.
Input: “1+2*3-4*5”
Output: -1
Approach to the Problem
This problem can be solved using Dynamic Programming. We need to consider all possible placements of parentheses for the given expression, so the Divide and Conquer technique will also be utilized.
1. Parsing the Expression
First, we need to separate the numbers and operators from the expression and store them in arrays. For example, we will convert the string “1+2*3-4*5” into the following format.
Number array: [1, 2, 3, 4, 5]
Operator array: ['+', '*', '-', '*']
2. Defining Dynamic Programming
Dynamic programming is a method that stores the results of each subproblem through several auxiliary arrays for future use. By using memoization, we can reduce time complexity by reusing results that have already been calculated.
3. Implementing the Recursive Function
We will calculate all possible combinations through a recursive function. This function divides based on the given index and calculates by placing parentheses differently for each side.
Swift Implementation
Below is the complete code implemented in the Swift programming language.
func minValue(expression: String) -> Int {
var numbers: [Int] = []
var operators: [Character] = []
// Step 1: Parse the expression
var currentNumber = ""
for char in expression {
if char.isNumber {
currentNumber.append(char)
} else {
numbers.append(Int(currentNumber)!)
operators.append(char)
currentNumber = ""
}
}
numbers.append(Int(currentNumber)!)
// Step 2: Create a memoization table
var memo: [[Int?]] = Array(repeating: Array(repeating: nil, count: numbers.count), count: numbers.count)
// Step 3: Define a recursive function
func compute(_ left: Int, _ right: Int, _ op: Character) -> Int {
switch op {
case '+': return left + right
case '-': return left - right
case '*': return left * right
default: fatalError("Unknown operator")
}
}
// Recursive function for minimum value
func findMinValue(left: Int, right: Int) -> Int {
if left == right {
return numbers[left]
}
if let result = memo[left][right] {
return result
}
var result = Int.max
for i in left..<right {="" let="" leftvalue="findMinValue(left:" left,="" right:="" i)="" rightvalue="findMinValue(left:" i="" +="" 1,="" right)="" computedvalue="compute(leftValue," rightvalue,="" operators[i])="" result="min(result," computedvalue)="" }="" memo[left][right]="result" return="" calculate="" the="" minimum="" value="" for="" whole="" expression="" findminvalue(left:="" 0,="" numbers.count="" -="" 1)="" <="" code=""></right>
<h3>Time Complexity Analysis</h3>
<p>The time complexity of this algorithm is O(N^3). N is the number of digits, as we need to evaluate the operators for each combination of two digits. However, due to the use of memoization, we do not recalculate the same subproblems repeatedly.</p>
<h3>Conclusion</h3>
<p>In this lecture, we covered the problem of "Finding Parentheses Arrangement that Minimizes Value" and explored the process of solving the problem and its implementation in Swift. I hope you achieve good results in coding tests through various approaches and optimization techniques to algorithm problems. Thank you!</p>
<p></p>
<div id="jp-relatedposts" class="jp-relatedposts">
<h3 class="jp-relatedposts-headline"><em>관련</em></h3>
</div>