문제 개요
숫자 n이 하나 주어져 있다고 가정해 봅시다. 이 숫자로부터 알파벳 소문자로 이루어진 문자열을 생성한 뒤, 해당 문자열이 회문(palindrome)인지 판별하는 것이 목표입니다. 여기서는 a부터 j까지만 사용하며, 각 문자는 숫자 한 자리와 대응됩니다. 즉, a = 0, b = 1, ..., j = 9 입니다.
예를 들어 숫자가 42라면, 각 자릿수에 대응하는 문자는 'e'(4)와 'c'(2)입니다. 자릿수의 합은 6(4+2)이므로 "ec"를 반복해 길이 6의 문자열 "ececec"을 만들고, 이 문자열이 회문인지 검사하게 됩니다.
입력이 n = 43이라면 출력은 True가 됩니다. 이 경우 생성되는 문자열은 "ededede"이며, 앞에서 읽으나 뒤에서 읽으나 같은 회문이기 때문입니다.
풀이 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- temp := 빈 문자열로 초기화
- s := n을 문자열로 변환
- letters := a부터 j까지의 모든 문자
- sum := 0으로 초기화
- substr := 빈 문자열로 초기화
- i를 0부터 s의 길이 - 1까지 반복:
- d := s[i]를 정수형 숫자로 변환
- substr := substr에 letters[d]를 이어 붙임
- sum := sum + d (자릿수 합 누적)
- temp의 길이가 sum 이하인 동안 반복:
- temp := temp에 substr을 이어 붙임
- temp := temp의 인덱스 0부터 sum - 1까지 잘라내기
- temp가 회문이면 true, 아니면 false 반환
예제 구현
아래 파이썬 코드를 통해 더 쉽게 이해할 수 있습니다.
def isPalindrome(s): return s == s[::-1] def solve(n): temp = "" s = str(n) letters = "abcdefghij" sum = 0 substr = "" for i in range(len(s)): d = int(s[i]) substr += letters[d] sum += d while len(temp) <= sum: temp += substr temp = temp[:sum] return isPalindrome(temp) n = 43 print(solve(n))
입력
43
출력
True
동작 원리 설명
먼저 숫자를 문자열로 변환한 후 각 자릿수를 순회하면서, 자릿값에 대응하는 알파벳 문자를 substr에 누적하고 동시에 자릿수의 합을 계산합니다. 예를 들어 43의 경우 substr은 "ed", sum은 7이 됩니다.
그다음 substr을 temp에 반복해서 붙인 뒤, 정확히 sum 길이만큼 잘라냅니다. 마지막으로 슬라이싱 기법 s == s[::-1]을 활용해 문자열을 뒤집은 것과 원본을 비교함으로써 회문 여부를 간단히 판별합니다.
시간 복잡도는 자릿수의 합에 비례하며, 공간 복잡도 역시 생성되는 문자열의 길이에 비례합니다. 따라서 입력 숫자의 자릿수 합이 작다면 매우 효율적으로 동작합니다.