17. Letter Combinations of a Phone Number

늘보·2021년 10월 31일

LeetCode

목록 보기

64/69

💡 풀이

var letterCombinations = function (digits) {
  if (!digits.length) return [];

  const map = {
    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 answer = [];

  const backTracking = (letter, index) => {
    let num = digits[index];
    let chars = map[num];

    if (index === digits.length) {
      answer.push(letter);
      return;
    }

    for (let c of chars) backTracking(letter + c, index + 1);
  };

  backTracking('', 0);
  return answer;
};

📝 결과

📝 정리

BackTracking의 기초적인 문제로 알고 있는 문제였는데, 이번에 BackTracking을 공부하면서 풀게 되었다. 이 알고리즘에 대한 간단한 설명은 여기 링크를 참고하면 좋을 것이다.

키패드는 다음과 같다.

먼저, 문제의 요구사항은 다음과 같다 digits = "23"이라는 input이 주어졌을 때, ["ad","ae","af","bd","be","bf","cd","ce","cf"] 다음과 같은 output이 나와야 한다.

그러니까 이 말은, "23"을 만드는 과정에서 생길 수 있는 모든 경우의 수를 구하라는 문제다. 그리고 backTracking 알고리즘은 가지치기를 통해 모든 경우의 수를 탐색하는 것이 아니고 효율적인 탐색을 할 수 있게 된다. 풀이는 다음과 같다.

먼저 전화번호를 mapping한 map 객체를 준비한다. 그리고 답을 담을 answer 배열도 준비한다.

  const map = {
    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 answer = [];

이후 backTracking이라는 재귀적으로 경우의 수를 탐색할 함수를 만들어준다. 함수의 arguments로는 몇 번째 digits에 해당하는지 나타내는 index와 몇 번째 단계까지 character가 만들어져 있는지를 나타내는 letter을 설정해줬다.
그리고 어떤 요소를 나타내는지, let num = digits[index]라고 설정해줬다.
chars 에는 매칭이 되는 character가 있는 배열을 담아준다. 이는 map 객체에서 가지고 온다. 예를 들어 num = 2라면, chars에는 ['a', 'b', 'c']가 들어올 것이다.
이후 'a'일때, 'b'일때, 'c'일때, 즉 모든 경우의 수를 탐색하기 위해서 반복문을 돌려준다. 이 반복문 안에서는 재귀적으로 backTracking 함수가 작동하는데, 다시 backTracking 함수가 작동할 때는 인자로 index+1, letter+c를 넣어준다.
그럼 마지막으로 어느 순간에는 재귀적인 함수 호출이 종료되는 순간이 오게 된다. 그 순간이 바로 index가 input인 digits.length와 같아지는 순간이 올 텐데, 그 이후부터는 더 이상 탐색할 것이 없기 때문에 answer 배열에 현재의 letter을 push 해주면 된다.
이렇게 모든 탐색이 끝나면 answer을 return 해주면 된다.