Python으로 8진수 숫자가 회문인지 확인하는 방법

어떤 숫자가 8진수 또는 10진수 형태로 주어졌다고 가정해 보겠습니다. 숫자가 8진수 형태라면 그대로 회문(palindrome)인지 확인하고, 10진수 형태라면 먼저 8진수로 변환한 뒤 회문 여부를 검사해야 합니다.

예를 들어 입력이 num = 178이라면 결과는 True입니다. 178에는 숫자 8이 포함되어 있는데, 8진수에서는 0부터 7까지만 사용할 수 있으므로 이 수는 10진수입니다. 178을 8진수로 변환하면 262가 되고, 262는 앞에서 읽어도 뒤에서 읽어도 같은 회문이므로 True가 출력됩니다.

문제 해결 접근 방식

이 문제는 다음 세 단계로 해결할 수 있습니다.

진법 판별: num의 모든 자릿수가 8 미만이면 이미 유효한 8진수이므로 자릿수를 그대로 추출하고, 8 이상의 자릿수가 하나라도 있으면 10진수로 간주하여 8진수로 변환합니다.
자릿수 추출: num이 0이 될 때까지 num을 base로 나눈 나머지를 리스트 끝에 추가하고, num을 몫으로 갱신합니다.
회문 검사: 리스트 양쪽 끝에서 시작하는 두 포인터를 중앙으로 이동시키며 값이 모두 일치하는지 확인합니다. 하나라도 다르면 False를 반환합니다.

구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

def is_all_under_8(num):
    # 모든 자릿수가 8 미만인지 확인
    while num > 0:
        if (num % 10) >= 8:
            return False
        num //= 10
    return True

def solve(num):
    # 8 이상의 자릿수가 있으면 10진수이므로 8진수로 변환
    base = 8 if not is_all_under_8(num) else 10
    oct_list = []
    while num != 0:
        oct_list.append(num % base)
        num //= base
    j = len(oct_list) - 1
    k = 0
    while k <= j:
        if oct_list[j] != oct_list[k]:
            return False
        j -= 1
        k += 1
    return True

num = 178
print(solve(num))

입력

출력

True

코드 설명

is_all_under_8() 함수는 숫자의 각 자릿수를 검사하여 8 이상인 자릿수가 존재하는지 확인합니다. 8진수 체계에서는 0~7의 숫자만 유효하기 때문에, 8 이상의 숫자가 발견되면 해당 수는 10진수임을 의미합니다.

solve() 함수는 판별된 진법에 따라 자릿수를 추출합니다. 10진수라면 8로 나눈 나머지를 차례대로 모아 8진수 표현을 만들고, 이미 8진수라면 10으로 나누어 원래 자릿수를 그대로 얻습니다. 이후 양쪽 끝에서부터 값을 비교하여 회문 여부를 최종 판단합니다.

복잡도 분석

자릿수 추출과 회문 검사 모두 자릿수 길이에 비례하여 수행되므로 시간 복잡도는 O(log n)이며, 자릿수를 저장하는 리스트로 인해 공간 복잡도 역시 O(log n)입니다.