문제 개요
0부터 9까지의 숫자로만 이루어진 문자열이 하나 주어지고, 목표값(target)이 주어집니다. 이때 숫자 사이에 이항 연산자 +, -, *를 삽입하여 목표값을 만들 수 있는 모든 가능한 조합을 반환해야 합니다.
예를 들어 입력이 "232"이고 목표값이 8이라면, 정답은 ["2*3+2", "2+3*2"]가 됩니다. 두 식 모두 계산 결과가 8이기 때문입니다.
풀이 접근 방법
이 문제는 백트래킹(backtracking) 기법으로 해결할 수 있습니다. 각 위치에서 숫자를 잘라내고 세 가지 연산자를 차례로 적용하며 재귀적으로 탐색하는 방식입니다. 핵심 로직은 다음과 같습니다.
- solve() 메서드 정의: 인덱스(idx), 문자열(s), 현재 누적값(curr), 목표값(target), 임시 식(temp), 곱셈용 값(mult)을 매개변수로 받습니다.
- idx가 문자열 길이 이상이 되면,
- curr이 target과 같다면 temp를 결과 리스트 ret의 끝에 추가합니다.
- 그 후 함수를 종료(return)합니다.
- aux를 빈 문자열로 초기화합니다.
- i를 idx부터 문자열 길이 미만까지 1씩 증가시키며 반복합니다.
- aux에 s[i]를 이어 붙입니다.
- aux의 첫 글자가 '0'이면서 길이가 1보다 크다면(선행 0 방지), 다음 반복으로 건너뜁니다.
- idx가 0인 경우(첫 숫자):
solve(i + 1, s, stol(aux), target, aux, stol(aux))를 호출합니다. - 그 외의 경우에는 세 가지 연산자를 각각 시도합니다.
- + 연산: solve(i + 1, s, curr + stol(aux), target, temp + "+" + aux, stol(aux))
- - 연산: solve(i + 1, s, curr - stol(aux), target, temp + "-" + aux, -stol(aux))
- * 연산: 곱셈은 일반 덧셈·뺄셈보다 우선순위가 높으므로, 직전에 더하거나 뺀 값을 되돌린 후 곱한 값을 다시 적용합니다.
solve(i + 1, s, curr - mult + mult * stol(aux), target, temp + "*" + aux, mult * stol(aux))
- 메인 함수에서 solve(0, num, 0, target, 빈 문자열, 0)을 호출하여 탐색을 시작합니다.
- 최종적으로 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;
}
typedef long long int lli;
class Solution {
public:
vector <string> ret;
void solve(int idx, string s, lli curr, lli target, string temp, lli mult){
if(idx >= s.size()){
if(target == curr){
ret.push_back(temp);
}
return;
}
string aux = "";
for(int i = idx; i < s.size(); i++){
aux += s[i];
if(aux[0] == '0' && aux.size() > 1) continue;
if(idx == 0){
solve(i + 1, s, stol(aux), target, aux, stol(aux));
} else {
solve(i + 1, s, curr + stol(aux), target, temp + "+" + aux, stol(aux));
solve(i + 1, s, curr - stol(aux), target, temp + "-" + aux, -stol(aux));
solve(i + 1, s, curr - mult + mult * stol(aux), target, temp + "*" + aux, mult * stol(aux));
}
}
}
vector<string> addOperators(string num, int target) {
solve(0, num, 0, target, "", 0);
return ret;
}
};
main(){
Solution ob;
print_vector(ob.addOperators("232", 8));
}입력
"232", 8
출력
[2+3*2, 2*3+2]
핵심 포인트 정리
- 연산자 우선순위 처리: 곱셈(*)은 덧셈·뺄셈보다 먼저 계산되므로, mult 매개변수에 직전 피연산자 값을 저장해 두었다가 curr에서 되돌린 뒤 곱셈 결과를 반영하는 것이 이 풀이의 핵심입니다.
- 선행 0 처리: "05"처럼 앞자리가 0이면서 두 자리 이상인 숫자는 유효하지 않으므로 continue로 건너뜁니다.
- 오버플로우 방지: long long int(lli) 타입을 사용해 중간 계산 과정에서의 오버플로우를 방지합니다.