문제 소개: 숫자–문자 매핑
1부터 9까지의 각 숫자가 여러 개의 문자에 대응되는 매핑이 다음과 같이 주어져 있다고 가정해 보겠습니다.
1 -> ['A', 'B', 'C'] 2 -> ['D', 'E', 'F'] 3 -> ['G', 'H', 'I'] 4 -> ['J', 'K', 'L'] 5 -> ['M', 'N', 'O'] 6 -> ['P', 'Q', 'R'] 7 -> ['S', 'T', 'U'] 8 -> ['V', 'W', 'X'] 9 -> ['Y', 'Z']
하나의 숫자가 주어졌을 때, 각 자릿수를 위 매핑 테이블의 문자로 치환하여 만들 수 있는 모든 문자열을 출력해야 합니다. 이때 지켜야 할 규칙은 두 가지입니다.
- 동일한 숫자는 항상 동일한 문자로: 같은 숫자가 숫자 안에서 여러 번 등장하면, 그 모든 위치에서 반드시 같은 문자를 사용해야 합니다.
- 입력 숫자에는 0이 포함되지 않습니다.
예를 들어 입력이 [4, 3, 5]라면, 4 → J/K/L, 3 → G/H/I, 5 → M/N/O를 조합한 총 27개의 문자열이 출력됩니다.
JGM KGM LGM JHM KHM LHM JIM KIM LIM JGN KGN LGN JHN KHN LHN JIN KIN LIN JGO KGO LGO JHO KHO LHO JIO KIO LIO
해결 알고리즘
이 문제는 앞서 만든 문자열들에 한 글자씩 이어 붙이며 차례대로 확장해 나가는 방식으로 해결할 수 있습니다. 핵심 아이디어는 딕셔너리(char_map)를 사용해 각 숫자가 처음 등장한 자릿수 위치를 기록해 두었다가, 같은 숫자가 다시 등장하면 이미 완성된 문자열에서 해당 위치의 문자를 꺼내 재사용하는 것입니다.
구체적인 처리 과정은 다음과 같습니다.
- 결과 리스트(
out), 임시 리스트(temp), 첫 등장 위치를 기록할 딕셔너리(char_map)를 준비하고 인덱스index를 0으로 초기화합니다. - 입력 숫자의 각 자릿수(
digit)에 대해 다음을 수행합니다.digit가char_map에 없다면 현재index를 저장합니다(첫 등장 위치).temp리스트를 비웁니다.- 매핑 테이블에서 해당 숫자에 대응하는 각 문자에 대해 반복합니다.
index == 0(첫 자릿수)이면 각 문자를 그대로out에 추가합니다.index > 0이면out의 모든 기존 문자열에 새 문자를 이어 붙여temp에 저장합니다. 단,char_map[digit] != index, 즉 이전에 등장한 숫자라면 기존 문자열에서char_map[digit]위치의 문자를 가져와 동일한 문자를 강제한 뒤 반복을 중단합니다.
index > 0이면temp의 복사본을out에 할당합니다.index를 1 증가시킵니다.
- 모든 자릿수를 처리한 뒤
out을 반환합니다.
Python 구현 예제
아래 코드를 통해 실제 동작을 확인해 보겠습니다.
def findCombinations(inp, table):
out = list()
temp = list()
char_map = dict()
index = 0
for digit in inp:
if digit not in char_map:
char_map[digit] = index
temp.clear()
for i in range(len(table[digit - 1])):
if index == 0:
s = table[digit - 1][i]
out.append(s)
if index > 0:
for string in out:
s = table[digit - 1][i]
if char_map[digit] != index:
s = string[char_map[digit]]
string = string + s
temp.append(string)
if char_map[digit] != index:
break
if index > 0:
out = temp.copy()
index += 1
return out
mapping = [['A', 'B', 'C'],
['D', 'E', 'F'],
['G', 'H', 'I'],
['J', 'K', 'L'],
['M', 'N', 'O'],
['P', 'Q', 'R'],
['S', 'T', 'U'],
['V', 'W', 'X'],
['Y', 'Z']]
inp = [4,3,5]
res = findCombinations(inp, mapping)
for it in res:
print(it, end=" ")실행 결과 확인
입력
[4,3,5]
출력
JGM KGM LGM JHM KHM LHM JIM KIM LIM JGN KGN LGN JHN KHN LHN JIN KIN LIN JGO KGO LGO JHO KHO LHO JIO KIO LIO
마무리 및 복잡도
이 알고리즘은 각 자릿수를 처리할 때마다 가능한 문자 수만큼 문자열을 곱셈적으로 늘려 나갑니다. 위 예제처럼 세 자릿수가 모두 3개의 문자에 대응된다면 최종 결과는 3 × 3 × 3 = 27개입니다. 일반적으로 결과 문자열의 개수는 각 자릿수에 대응되는 문자 개수들의 곱이 되며, 자릿수가 늘어날수록 지수적으로 증가하므로 입력 길이에 유의해야 합니다. 반면 같은 숫자가 반복되는 경우에는 해당 자릿수의 문자 선택지가 1개로 고정되기 때문에, 결과의 총 개수는 숫자의 중복 여부에 따라 달라집니다.