숫자와 연산자를 조합하여 타겟 만들기 (Backtracking) | 알고리즘 & 영어 공부

1️⃣ 문제 설명 (Problem Statement)

📌 영어 지문 (Original Problem Statement)

Given a string num that contains only digits and an integer target,

return all possibilities to insert the binary operators +, -, and/or * between the digits of num

so that the resultant expression evaluates to the target value.

Constraints:

• 1 <= num.length <= 10
• num consists of only digits.
• -231 <= target <= 231 - 1

📌 한글 번역 (Korean Translation)

숫자로만 이루어진 문자열 num과 정수 target이 주어졌을 때,

num의 각 자리 숫자 사이에 +, -, * 연산자를 적절히 삽입하여 식을 만들고,

그 결과값이 target이 되는 모든 경우를 찾는 문제입니다.

 

제약 사항:

• num의 길이는 1 이상 10 이하입니다.
• num은 숫자로만 이루어져 있습니다.
• target 값의 범위는 -231 이상 231 - 1 이하입니다.

---

2️⃣ 예제 (Example)

입력	출력
num = "123", target = 6	["1*2*3", "1+2+3"]
num = "232", target = 8	["2*3+2", "2+3*2"]
num = "3456237490", target = 9191	[]

 

• "123"의 경우 1+2+3 = 6 또는 1*2*3 = 6이므로 두 가지 정답이 존재합니다.
• "232"의 경우 2*3+2 = 8, 2+3*2 = 8이므로 두 가지 정답이 있습니다.
• "3456237490"에서는 9191을 만들 방법이 없으므로 빈 배열을 반환합니다.

---

🚀 여러 가지 문제 해결 전략 (How to Solve This Problem Efficiently?)

1️⃣ 완전 탐색 (Brute Force)

모든 연산자 조합을 시도하여 num의 모든 경우를 탐색한 후, 값이 target과 일치하는지 확인하는 방식입니다.
하지만 연산자가 3가지(+, -, *)이고, 숫자 사이에 연산자를 삽입하는 경우의 수가 많아지므로 비효율적입니다.

2️⃣ 백트래킹 (Backtracking)

불필요한 연산을 줄이면서 가능한 경우만 탐색하는 방식입니다.
특히, * 연산이 존재할 때, 기존 연산을 어떻게 처리해야 하는지가 핵심입니다.

---

💡 어떤 방식을 사용해야 될까?

✨ 풀이 방법 1: 완전 탐색 (Brute Force, 비효율적인 방식)

• 모든 가능한 연산자 조합을 시도한 후, 결과값이 target과 일치하는지 확인하는 방법.
• 문자열의 길이가 n일 때, 연산자를 삽입할 수 있는 위치는 n-1개.
• 각 위치에 +, -, * 세 가지 연산자를 넣을 수 있으므로 **O(3^(n-1))**의 시간 복잡도를 가짐.

단점:

• num의 길이가 10이면 최악의 경우 3^9 ≈ 19,683번 연산을 수행해야 하므로 비효율적.

---

✨ 풀이 방법 2: 백트래킹 (Backtracking, 효율적인 방식)

• 연산자를 삽입하면서 불필요한 경우를 조기에 제거하는 방식.
• * 연산은 이전 값과 결합되어야 하므로 previousOperand를 유지하여 처리.

장점:

• 불필요한 연산을 줄여 연산 속도를 개선할 수 있음.
• num의 길이가 10이더라도 모든 경우를 탐색하지 않으므로 성능이 향상됨.

---

3️⃣ TypeScript 코드 

function addOperators(num: string, target: number): string[] {
    const result: string[] = [];

    function backtrack(index: number, currentExpr: string, currentValue: number, previousOperand: number): void {
        // 문자열을 끝까지 탐색했을 때, 현재 계산된 값이 target과 일치하면 결과에 추가
        if (index === num.length) {
            if (currentValue === target) {
                result.push(currentExpr);
            }
            return;
        }

        for (let i = index; i < num.length; i++) {
            // 부분 숫자 가져오기
            const subNumStr = num.substring(index, i + 1);
            const subNum = parseInt(subNumStr, 10);

            // 앞에 0이 붙는 숫자는 허용하지 않음 (예: "05"는 불가능)
            if (subNumStr.length > 1 && subNumStr[0] === '0') {
                break;
            }

            if (index === 0) {
                // 첫 번째 숫자는 연산자 없이 추가
                backtrack(i + 1, subNumStr, subNum, subNum);
            } else {
                // 덧셈 연산 (`+`)
                backtrack(i + 1, currentExpr + "+" + subNumStr, currentValue + subNum, subNum);
                // 뺄셈 연산 (`-`)
                backtrack(i + 1, currentExpr + "-" + subNumStr, currentValue - subNum, -subNum);
                // 곱셈 연산 (`*`)
                backtrack(
                    i + 1, 
                    currentExpr + "*" + subNumStr, 
                    currentValue - previousOperand + previousOperand * subNum, 
                    previousOperand * subNum
                );
            }
        }
    }

    // 백트래킹 시작
    backtrack(0, "", 0, 0);
    return result;
}

// 테스트
console.log(addOperators("123", 6));   // ["1*2*3", "1+2+3"]
console.log(addOperators("232", 8));   // ["2*3+2", "2+3*2"]
console.log(addOperators("3456237490", 9191));  // []

---

🚀 영어 표현 정리

영어 표현 한국어 의미

Given a string num	문자열 num이 주어졌을 때
Insert binary operators	이항 연산자를 삽입하다
Evaluate to the target value	목표 값으로 계산되다
Backtracking to explore possibilities	가능한 경우를 탐색하는 백트래킹
Avoid leading zeros	앞에 0이 붙는 숫자를 피하다

---

🔥 결론

이 문제는 연산자 삽입과 연산 우선순위 처리가 중요한 백트래킹 (Backtracking) 문제입니다.
단순한 완전 탐색보다 이전 연산 결과를 추적하는 방식이 효율적입니다.
이 문제를 이해하면 다른 수식 조합 관련 문제도 쉽게 해결할 수 있을 것입니다! 🚀