[Algorithm][LeetCode 2094][Easy] Finding 3-Digit Even Numbers

<문제>

You are given an integer array digits, where each element is a digit. The array may contain duplicates.

You need to find all the unique integers that follow the given requirements:

• The integer consists of the concatenation of three elements from digits in any arbitrary order.
• The integer does not have leading zeros.
• The integer is even.

Return a sorted array of the unique integers.

Example 1:

Input: digits = [2,1,3,0]
Output: [102,120,130,132,210,230,302,310,312,320]
Explanation: All the possible integers that follow the requirements are in the output array.
Notice that there are no odd integers or integers with leading zeros.

Example 2:

Input: digits = [2,2,8,8,2]
Output: [222,228,282,288,822,828,882]
Explanation: The same digit can be used as many times as it appears in digits.
In this example, the digit 8 is used twice each time in 288, 828, and 882.

Example 3:

Input: digits = [3,7,5]
Output: []
Explanation: No even integers can be formed using the given digits.

<솔루션>

1. brute force 방식

1.1 핵심 로직

1. 미리 주어진 배열의 요소의 map을 만들어 놓는다.
2. 100 ~ 999 까지 숫자 중 짝수만 순회하면서, 해당 숫자를 주어진 배열 내의 숫자로 만들 수 있는지 체크한다.
3. 만들 수 있다면, result에 추가한다.

1.2 코드

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var findEvenNumbers = function(digits) {
    const result = [];
    const originalMap = {};
    for (let digit of digits) {
        originalMap[digit] = originalMap[digit] ? originalMap[digit] + 1 : 1;
    }

    for (let i = 100; i < 999; i = i + 2) {
        let isChecked = true;
        let splitedI = i.toString().split('');
        let copiedMap = JSON.parse(JSON.stringify(originalMap));
        for (let num of splitedI) {
            if (!copiedMap[num] || copiedMap[num] - 1 < 0) {
                isChecked = false;
                break;
            } else {
                copiedMap[num]--;
            }
        }
        if (isChecked) result.push(i);
    }
    return result;
};

1.3 느낀점

• 문제의 제약조건을 확인해보고 brute force 방식을 사용하는 것도 나쁜 전략이 아니라는 것을 알았다.
• 보통 알고리즘을 풀다 보면 배열을 순회하면서 공식을 찾으려고 하는데, 이번 문제는 brute force 방식이 더 직관적이고 깔끔하다는 느낌이 들었다.
• 제약조건을 주의 깊게 확인하지 않고 풀었던 과거 습관을 다시 돌아보게 되었다. 이런 습관은 꼭 고쳐야 한다.

2. 숫자를 조합해서 푸는 방식 (3중 for문 접근 방식)

2.1 핵심 로직

1. 중복을 고려한 세 자리 순열을 생성한다.
2. 중복된 결과를 제거한다. (Set 자료 구조 이용)
3. 맨 앞자리가 0인 숫자는 제거한다.
4. 끝 자리가 짝수인 숫자만 남긴다.

2.2 코드

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var findEvenNumbers = function(digits) {
    const result = new Set();
    const len = digits.length;

    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len; j++) {
            if (j === i) continue;
            for (let k = 0; k < len; k++) {
                if (k === i || k === j) continue;

                const a = digits[i];
                const b = digits[j];
                const c = digits[k];

                if (a === 0) continue;
                if (c % 2 !== 0) continue;

                const num = a * 100 + b * 10 + c;
                result.add(num);
            }
        }
    }

    return Array.from(result).sort((a, b) => a - b);
}

3. 백 트래킹 방식

3.1 백트래킹이란?

백트래킹은 재귀 + 가지치기의 조합으로, 가능한 모든 조합을 시도하되 조건이 안 맞으면 조기에 중단하고 돌아가는 알고리즘이다.

3.2 왜 백트래킹이 필요한가?

예를 들어 [1, 2, 3, 0]에서 중복 없이 3자리 숫자를 조합하고 싶을 때:

• digits 배열에서 서로 다른 인덱스를 골라야 하고,
• 선택한 조합이 조건을 만족하는지 확인해야 한다.

→ 이런 경우, 수동 구현보다 백트래킹이 더 명확하고 깔끔하다.

3.3 코드

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var findEvenNumbers = function(digits) {
    const result = new Set();
    const used = Array(digits.length).fill(false);

    function backtrack(path) {
        if (path.length === 3) {
            const [a, b, c] = path;
            if (a === 0) return;
            if (c % 2 !== 0) return;

            const num = a * 100 + b * 10 + c;
            result.add(num);
            return;
        }

        for (let i = 0; i < digits.length; i++) {
            if (used[i]) continue;

            used[i] = true;
            path.push(digits[i]);
            backtrack(path);
            path.pop();
            used[i] = false;
        }
    }

    backtrack([]);
    return Array.from(result).sort((a, b) => a - b);
};

세 가지 방식 비교

항목	1. Brute Force 방식	2. 3중 for문 방식	3. 백트래킹 방식
핵심 전략	100~999 중 짝수만 돌며 digits로 만들 수 있는지 검사	digits 배열로 만들 수 있는 3자리 순열을 모두 생성	재귀로 모든 조합을 탐색하며 조건에 맞는 수만 수집
중복 관리	맵으로 개수 비교하여 허용된 사용량만 사용	인덱스 비교로 중복 제거	used[] 배열로 인덱스 중복 방지
성능 (효율)	숫자 후보 450개만 체크하므로 매우 효율적	빠르지만 중복 체크 필요	유연하나 재귀 호출이 많아 다소 무거울 수 있음
가독성	직관적이며 조건 기반으로 깔끔	간단하지만 중복 방지 로직 필요	구조는 깔끔하나 익숙하지 않으면 어렵게 느껴질 수 있음
조건 반영 시점	숫자 전체 생성 후 조건 확인	조합 생성 중 조건 체크	조합 도중 조건 미달 시 바로 가지치기
중복 제거	Map 기반 개수 제한	Set으로 중복 방지	Set으로 중복 방지
적합한 상황	값의 범위가 제한되어 있을 때	digits가 작고 단순 조합일 때	조건이 복잡하거나 범위가 클 때
난이도	★☆☆ (가장 쉬움)	★★☆ (보통)	★★★ (난이도 높음)

요약

• Brute Force: 가장 직관적이며 조건이 명확할 때 적합
• 3중 for문: 배열이 작을 때 빠르게 적용 가능
• 백트래킹: 조건이 복잡하거나 유연한 탐색이 필요할 때 적합