숫자와 연산자로 이루어진 문자열이 주어졌을 때, 숫자와 연산자를 다양한 방식으로 묶어서(즉, 괄호를 서로 다르게 배치해서) 얻을 수 있는 모든 가능한 결과값을 찾아야 합니다. 이 문제에서 사용할 수 있는 유효한 연산자는 + , - , * 세 가지입니다.
예를 들어 입력이 "2*3-4*5"라고 한다면, 출력은 [-34, -14, -10, -10, 10]이 됩니다. 그 이유는 다음과 같습니다.
- (2*(3-(4*5))) = -34
- ((2*3)-(4*5)) = -14
- ((2*(3-4))*5) = -10
- (2*((3-4)*5)) = -10
- (((2*3)-4)*5) = 10
문제 해결 접근 방법
이 문제는 분할 정복(Divide and Conquer)과 메모이제이션(Memoization)을 활용하면 효율적으로 해결할 수 있습니다. 각 연산자를 기준으로 식을 둘로 나눈 뒤, 좌측과 우측에서 나올 수 있는 모든 값들의 조합을 계산하는 방식입니다. 단계별로 살펴보겠습니다.
- 메모이제이션용 맵(memo)을 정의합니다.
- solve() 메서드를 정의하고, 입력 문자열을 인자로 전달합니다.
- 결과를 담을 배열 ret을 생성합니다.
- memo에 해당 입력 문자열이 이미 존재한다면 memo[input]을 그대로 반환합니다.
- i를 0부터 입력 문자열의 크기까지 반복합니다.
- input[i]가 지원되는 연산자(+, -, *)라면 다음을 수행합니다.
- part1 := solve(0부터 i-1까지의 부분 문자열)
- part2 := solve(i+1부터 문자열 끝까지의 부분 문자열)
- j를 0부터 part1의 크기까지, k를 0부터 part2의 크기까지 반복하면서
- input[i]가 '+'라면 part1[j] + part2[k]를 ret에 추가합니다.
- input[i]가 '*'라면 part1[j] * part2[k]를 ret에 추가합니다.
- input[i]가 '-'라면 part1[j] - part2[k]를 ret에 추가합니다.
- input[i]가 지원되는 연산자(+, -, *)라면 다음을 수행합니다.
- 반복 종료 후 ret이 비어 있다면, 이는 입력에 연산자가 없는 순수한 숫자라는 의미이므로 입력 문자열을 정수로 변환하여 반환합니다.
- memo[input] := ret을 저장한 뒤 ret을 반환합니다.
C++ 구현 예시
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
map <string, vector<int>> memo;
vector<int> diffWaysToCompute(string input) {
vector <int> ret;
if(memo.count(input)) return memo[input];
for(int i = 0; i < input.size(); i++){
if(input[i] == '+' || input[i] == '*' || input[i] == '-'){
vector <int> part1 = diffWaysToCompute(input.substr(0, i));
vector <int> part2 = diffWaysToCompute(input.substr(i + 1));
for(int j = 0; j < part1.size(); j++ ){
for(int k = 0; k < part2.size(); k++){
if(input[i] == '+'){
ret.push_back(part1[j] + part2[k]);
}
else if(input[i] == '*'){
ret.push_back(part1[j] * part2[k]);
} else {
ret.push_back(part1[j] - part2[k]);
}
}
}
}
}
if(ret.empty()){
ret.push_back(stoi(input));
}
return memo[input] = ret;
}
};
main(){
Solution ob;
print_vector(ob.diffWaysToCompute("2*3-4*5"));
}입력
"2*3-4*5"
출력
[-34, -10, -14, -10, 10]
출력 결과의 순서는 재귀 호출과 맵의 내부 처리 순서에 따라 달라질 수 있으며, 포함된 값들은 동일합니다. 이처럼 분할 정복과 메모이제이션을 결합하면 중복 계산을 줄여 같은 부분식이 여러 번 등장할 때도 빠르게 답을 얻을 수 있습니다.