본문 바로가기
개발/알고리즘

[LeetCode] 17. Letter Combinations of a Phone Number (javascript)

by 자몬다 2021. 5. 31.
728x90

전화기의 숫자 버튼 2~9에는 영문자가 적혀 있다.

주어진 숫자로 조합 가능한 영문자 배열을 리턴하는 문제이다.

 

2번 버튼은 abc, 3번 버튼엔 def라고 적혀있다면

['a', 'b', 'c'] 를 만들고

배열을 반복을 돌면서 각 요소마다 다음 버튼의 문자열을 붙여주는 방식으로 해결했다.

[['ad', 'ae', 'af'], 'b', 'c']

[['ad', 'ae', 'af'], ['bd', 'be', 'bf'], 'c']

[['ad', 'ae', 'af'], ['bd', 'be', 'bf'], ['cd', 'ce', 'cf']]

그리고 배열을 평탄화해준다.

또 다음 버튼이 있다면 평탄화된 배열에 대하여 똑같이 반복한다.

 

구상은 쉽게 했는데, 중간에 전화기 버튼 객체가 오염되는 문제가 있어 시간을 허비했다.

분명 btns를 수정하거나 재정의하는 코드가 없는데도 btns가 자꾸 오염되어

어쩔 수 없이 반복문 안에서 재정의해주었다.. 리트코드의 버그인 듯 하다.

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
    if (digits.length === 0) return [];
    // 전화기 버튼 객체
    const btns = {
        2: ['a', 'b', 'c'],
        3: ['d', 'e', 'f'],
        4: ['g', 'h', 'i'],
        5: ['j', 'k', 'l'],
        6: ['m', 'n', 'o'],
        7: ['p', 'q', 'r', 's'],
        8: ['t', 'u', 'v'],
        9: ['w', 'x', 'y', 'z'],
    };
    let result = btns[digits[0]];
    if (digits.length === 1) return result;

    // 첫 digits로 이루어진 조합은 이미 구했으므로,
    // 주어진 digits 길이-1 만큼만 반복을 돈다. "235" => "35"
    for (let i = 1; i < digits.length; i++) {
        // 이유는 알수없으나 btns 객체가 오염되는 버그가 있어 부득이하게 재정의
        const btns = {
            2: ['a', 'b', 'c'],
            3: ['d', 'e', 'f'],
            4: ['g', 'h', 'i'],
            5: ['j', 'k', 'l'],
            6: ['m', 'n', 'o'],
            7: ['p', 'q', 'r', 's'],
            8: ['t', 'u', 'v'],
            9: ['w', 'x', 'y', 'z'],
        };
        // 추가해야할 버튼의 문자열 배열
        const chars = btns[digits[i]];
        // 문자열 4개짜리 버튼이면 4개를 추가해주어야 한다.
        const isFourChars = digits[i] === '7' || digits[i] === '9';

        // 만들어진 배열을 반복을 돌면서, 새로운 문자열을 더한 배열로 대체한다.
        for (let j = 0; j < result.length; j++) {
            const str = result[j];
            result[j] = [str + chars[0], str + chars[1], str + chars[2]];
            if (isFourChars) result[j].push(str + chars[3]);
        }

        // 2차배열을 flatten해준다.
        result = result.flat();
    }

    return result;
};

댓글0