JavaScript 알고리즘: 인코딩된 숫자 메시지를 알파벳 조합으로 디코딩하기

문제 정의

a = 1, b = 2, … z = 26과 같은 알파벳-숫자 매핑 규칙이 주어져 있고, 이 규칙에 따라 인코딩된 하나의 메시지가 전달된다고 가정해 보겠습니다. 우리가 작성해야 할 것은 이 메시지를 입력받아 처리하는 JavaScript 함수입니다.

함수의 목표는 주어진 메시지를 디코딩할 수 있는 서로 다른 방법의 총 개수를 계산하는 것입니다.

'111' 예제 살펴보기

예를 들어 메시지 '111'의 답은 3입니다. 아래처럼 세 가지 방식으로 해석할 수 있기 때문입니다.

aaa — 1 / 1 / 1 (각 숫자를 한 글자씩 해석)
ka — 11 / 1 (앞의 두 자리를 묶어 k로 해석)
ak — 1 / 11 (뒤의 두 자리를 묶어 k로 해석)

JavaScript 구현 코드

이 문제는 재귀(recursion)를 활용하면 직관적으로 풀 수 있습니다. 구현 코드는 다음과 같습니다.

const waysToProcess = (message, ways = 0) => {
  if (message.length) {
    // 먼저 한 글자만 잘라내는 경우를 탐색
    ways = waysToProcess(message.slice(1, message.length), ways);
    const numCurr = parseInt(message[0]);
    const numNext = "undefined" === typeof message[1] ? null : parseInt(message[1]);
    // 두 자리를 하나의 알파벳으로 묶을 수 있는지 검사
    if (numCurr && numNext && numCurr < 3 && numCurr + numNext < 27) {
      ways = waysToProcess(message.slice(2, message.length), ways);
    }
  } else {
    // 문자열을 모두 소진하면 하나의 완성된 디코딩 경로
    ways++;
  }
  return ways;
};

console.log(waysToProcess('111'));

코드 동작 원리

이 알고리즘은 재귀 호출을 기반으로 다음과 같이 동작합니다.

종료 조건: 더 이상 처리할 문자가 없으면(빈 문자열), 지금까지의 분할이 하나의 유효한 디코딩으로 완성되었다는 뜻이므로 경우의 수를 1 증가시킵니다.
한 글자 처리: 항상 첫 번째 숫자 하나를 단독 알파벳으로 해석하는 경우를 먼저 고려해, 나머지 문자열에 대해 재귀 호출을 진행합니다.
두 글자 처리: 현재 숫자와 바로 다음 숫자가 존재하고, 두 자리를 하나의 알파벳(10~26 범위)으로 묶을 수 있다면 앞의 두 글자를 함께 제거한 뒤 재귀 호출하여 추가 경우의 수를 누적합니다.

가능한 모든 분할 경로가 빈 문자열에 도달할 때마다 카운터가 증가하며, 모든 재귀 호출이 끝난 뒤 반환되는 값이 곧 전체 디코딩 경우의 수가 됩니다.

참고로 이 방식은 최악의 경우 지수 시간 복잡도(O(2ⁿ))를 가질 수 있습니다. 입력 문자열이 길어지면 중복 계산을 줄이기 위해 메모이제이션(Memoization)이나 동적 계획법(DP)으로 최적화하는 것이 좋습니다.

실행 결과

위 코드를 실행하면 콘솔에 다음과 같이 출력됩니다.