Python으로 숫자 문자열을 알파벳으로 해독하는 방법

이번 글에서는 숫자('0'~'9')와 '#' 기호로만 구성된 문자열 s를 영어 소문자 알파벳으로 변환(디코딩)하는 문제를 단계별로 살펴보겠습니다.

문제 정의

주어진 문자열은 아래 규칙에 따라 알파벳으로 매핑됩니다.

• 'a'부터 'i'까지의 문자는 각각 '1'부터 '9'에 대응됩니다.
• 'j'부터 'z'까지의 문자는 각각 '10#'부터 '26#'에 대응됩니다.

예를 들어 입력이 "10#11#12"라면, 10#은 j, 11#은 k에 대응되고 마지막의 1과 2는 각각 a와 b에 대응되므로 결과는 "jkab"가 됩니다. 이 문제에서는 항상 유일한 매핑이 존재한다고 가정합니다.

풀이 접근 방법

이 문제는 문자열을 뒤에서부터(오른쪽에서 왼쪽으로) 탐색하면 깔끔하게 해결할 수 있습니다. '#'을 만나면 바로 앞의 두 자리를 하나의 숫자로 묶어 처리하고, 일반 숫자는 한 글자씩 처리하면 됩니다.

1. 숫자(1~26)에 대응하는 알파벳을 미리 저장할 맵(딕셔너리)을 생성합니다.
2. 결과 문자열 ans를 빈 값으로 초기화하고, 인덱스 i를 문자열의 마지막 위치로 설정합니다.
3. i가 유효한 동안 다음을 반복합니다.
   • s[i]가 '#'이라면 앞의 두 문자를 합쳐 temp를 만들고, map[temp]를 결과 앞에 추가한 뒤 i를 3만큼 감소시킵니다.
   • 그렇지 않다면 map[s[i]]를 결과 앞에 추가하고 i를 1만큼 감소시킵니다.
4. 탐색이 끝나면 완성된 문자열 ans를 반환합니다.

Python 구현 예제

아래 코드로 위 접근 방식을 확인해 보겠습니다.

class Solution(object):
    def freqAlphabets(self, s):
        m = {}
        x = 'a'
        for i in range(1, 27):
            m[str(i)] = x
            x = chr(ord(x) + 1)
        ans = ""
        m[''] = ''
        i = len(s) - 1
        while i >= 0:
            if s[i] == "#":
                temp = ""
                for j in range(i - 2, i):
                    temp += s[j]
                ans = m[temp] + ans
                i -= 3
            else:
                ans = m[s[i]] + ans
                i -= 1
        return ans

ob1 = Solution()
print(ob1.freqAlphabets("17#123#5621#"))

실행 결과

입력:

"17#123#5621#"

출력:

qawefu

동작 원리 살펴보기

입력 "17#123#5621#"가 어떻게 "qawefu"로 변환되는지 뒤에서부터 추적해 보겠습니다.

• "21#" → u
• '6' → f, '5' → e
• "23#" → w
• '1' → a
• "17#" → q

앞에서부터 읽으면 q, a, w, e, f, u 순서이므로 최종 결과는 "qawefu"가 됩니다.

복잡도 분석

문자열의 길이를 n이라 할 때, 모든 문자를 한 번씩만 방문하므로 시간 복잡도는 O(n)입니다. 결과 문자열과 맵을 저장하기 위해 O(n)의 공간 복잡도가 필요합니다.