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

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

💡 구글에 Javascript 풀이가 많이 없거나, 배운 점이 있으면 포스팅합니다.

내 풀이

/**
 * @param {string} digits
 * @return {string[]}
 */
//숫자들이 주어진다.
// 숫자들은 각 후보가 주어진다.
// 숫자들을 돌면서 어떤 후보가 뽑힐수있는지 모든 경우의 수를 잡는다.

const letterMap = ['','','abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz' ]
var letterCombinations = function(digits) {
    const result = []
    const visited = Array(digits.length).fill().map((x) => Array(0))
    const tmp = []
    function DFS(index) {
        if (index === digits.length) {
            if (tmp.length === 0) return []
            result.push(tmp.join(''))
        } else {
            const digit = digits[index]
            const letter = letterMap[digit]
            for (let i = 0; i < letter.length; i++) {
                if (!visited[index][i]) {
                    visited[index][i] = true
                    tmp.push(letter[i])
                    DFS(index + 1)
                    tmp.pop()
                    visited[index][i] = false
                }
            } 
        }
    }

    DFS(0)
    return result
};

• DFS를 활용하면 간단하게 풀리겠다. 싶어서 하던대로 풀어봤습니다.
• 정답을 받고 나서 다른 사람의 풀이를 봤는데 또 깜짝놀랬습니다. ㅎㅎ

다른 사람 풀이

const letterCombinations = (digits) => {
  if (digits == null || digits.length === 0) return [];

  const map = ['','','abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz' ]

  const res = [];
  const go = (i, s) => {
    if (i === digits.length) {
      res.push(s);
      return;
    }

    for (const c of map[digits[i]]) {
      go(i + 1, s + c);
    }
  };

  go(0, '');
  return res;
};

다른 사람 풀이를 통해 배운 점

1) 함수에 들어오자 마자 예외처리를 해준 점

  if (digits == null || digits.length === 0) return [];

⇒ 난 생각없이 submit을 한 뒤, 빈 인풋 케이스가 있다는 걸 확인 하고 DFS함수 내에 부랴부랴 예외처리를 넣어주었다.

이거 면접 시 라이브코딩할 때도 정답은 맞췄지만 예외처리 하지 않아서 살짝 부끄러웠던? 경험이 있던거와 같은 상황인데, 지금 부터는 문제풀이 할 때 부터 항상 예외처리를 신경쓰면서 진행하기로 한다.

2) 파라미터를 활용해서 편하게 푼 점

⇒ 난 tmp 배열을 활용해서 join()으로 풀었다. 문자열로 하고 싶었지만, 재귀 스택 나온뒤에 다음 레터로 넘어갈때 pop()해주는 과정을 어떻게 할지 몰라서 배열로 간단하게 처리했는데, 그것보다 파라미터를 활용했으면 훨씬 간단하게 해결이 되었었다.

위 2가지가 가장 큰 차이점인 것 같다. 한번 다시 풀어보자. 하던대로가 아니라 항상 조금씩 발전해야지… 이게 생각보다 꽤나 고통스러운 과정인데, 이런 “의도적 훈련 과정”이 실력을 키워주겠지 😭

참고해서 푼 풀이

const map = ['','','abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz' ]
var letterCombinations = function(digits) {
    if (digits === null || digits.length === 0) return []

    const result = []
    const visited = Array(digits.length).fill().map((x) => Array(0))
    function DFS (index, str) {
        if (index === digits.length){
            result.push(str)
        } else {
            const letter = map[digits[index]]
            for (let i = 0; i < letter.length; i++) {
                if (!visited[index][i]) {
                    visited[index][i] = true
                    DFS(index + 1, str + letter[i])
                    visited[index][i] = false
                }
            }
        }
    }
    DFS(0, '')

    return result
};

문제점 또는 차이점

1) 다른 사람 풀이에선 얼리리턴 패턴을 사용해서 else문을 없앴다. ⇒ 뎁스가 줄어들어 보기가 훨씬 편한다.

⇒ 적용 코드

const map = ['','','abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz' ]
var letterCombinations = function(digits) {
    if (digits === null || digits.length === 0) return []

    const result = []
    const visited = Array(digits.length).fill().map((x) => Array(0))
    function DFS (index, str) {
        if (index === digits.length){
            result.push(str)
            return
        }

        const letter = map[digits[index]]
        for (let i = 0; i < letter.length; i++) {
            if (!visited[index][i]) {
                visited[index][i] = true
                DFS(index + 1, str + letter[i])
                visited[index][i] = false
            }
        }
    }
    DFS(0, '')

    return result
};

2) visited 배열을 통한 방문처리를 하지 않았다. 근데 이렇게 하면 보기는 깔끔한데 훨씬 많은 경우의 수를 확인하게 될것 같다.

⇒ 전혀 아니다. ㅋㅋㅋㅋㅋ 내 코드에선 visited가 전혀 의미가 없는 코드였었다.

어차피 [index][i] 라서 한번 이외에 방문할 경우의수가 없는 상황이었다. 하… 바본가 ㅎㅎ

최종 코드

/**
 * @param {string} digits
 * @return {string[]}
 */
const map = ['','','abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz' ]
var letterCombinations = function(digits) {
    if (digits === null || digits.length === 0) return []

    const result = []
    function DFS (index, str) {
        if (index === digits.length){
            result.push(str)
            return
        }

        const letter = map[digits[index]]
        for (let i = 0; i < letter.length; i++) {
            DFS(index + 1, str + letter[i])
        }
    }
    DFS(0, '')

    return result
};

// Previous code

// const letterMap = ['','','abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz' ]
// var letterCombinations = function(digits) {
//     if (digits === null || digits.length === 0) return []

//     const result = []
//     const visited = Array(digits.length).fill().map((x) => Array(0))
//     const tmp = []
//     function DFS(index) {
//         if (index === digits.length) {
//             result.push(tmp.join(''))
//         } else {
//             const digit = digits[index]
//             const letter = letterMap[digit]
//             for (let i = 0; i < letter.length; i++) {
//                 if (!visited[index][i]) {
//                     visited[index][i] = true
//                     tmp.push(letter[i])
//                     DFS(index + 1)
//                     tmp.pop()
//                     visited[index][i] = false
//                 }
//             } 
//         }
//     }

//     DFS(0)
//     return result
// };

최종 코드는 위와 같다. 사실상 베스트 코드를 따라한 수준으로 변했지만, 어떤점에서 차이점이 있었는지 차근차근 따라가 본 것 자체가 꽤 공부가 되었지 않나 싶다. 앞으로도 DFS 문제를 많이 만날텐대 매번 좋지 못한 풀이로 정답을 맞기보단 이렇게 (조금 괴롭지만) 차근차근 코드를 발라내면 실력이 향상되지 않을까 싶다.

LeetCode가 웹개발 실무에 도움이 되는가? 하는 의문이 많다는걸 잘 알고 있다. 하지만 이런 과정이 없이 웹개발 실무만 한다면 예외처리 하는 연습, 시간복잡도를 생각하며 코딩하는 습관, 다른 사람 코드를 보며 좋은 코드로 개선하는 과정을 겪어보지 못했을텐대 그렇게 실무만 하는것이 과연 좋은것인가? 의문이다.

개인적으로 문제풀이는 재미도 있고, 도움도 되는 활동이라 생각한다. (천재가 아니라 살짝 고통스럽긴하다 ㅎㅎ 헬스하면 건강해져서 좋지만 할 떄마다 힘든거랑 비슷한듯)