Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬에서 큰 숫자의 자릿수 순열이 8로 나누어 떨어지는지 확인하는 방법

문자열 형태로 주어진 아주 큰 숫자가 있고, 그 숫자의 자릿수를 임의로 재배열한 결과 중 하나라도 8로 나누어 떨어지는지 판별해야 한다고 가정해 보겠습니다. 숫자가 문자열로 주어지기 때문에 단순한 정수 연산만으로는 처리하기 어렵습니다.

예를 들어 입력이 input_num = "4696984"라면, 자릿수를 재배열해 마지막 세 자리를 984(8 × 123)로 만들 수 있으므로 출력은 "Divisible by eight"(8로 나누어 떨어짐)가 됩니다.

핵심 원리: 마지막 세 자리만 확인하면 된다

1000이 8의 배수이기 때문에, 어떤 정수를 8로 나눈 나머지는 오직 마지막 세 자리에 의해서만 결정됩니다. 따라서 전체 자릿수의 모든 순열을 직접 만들어 볼 필요 없이 다음과 같이 접근할 수 있습니다.

  • 입력 숫자의 각 자릿수 빈도를 계산한다.
  • 세 자리 8의 배수(104부터 992까지 8씩 증가)를 모두 순회한다.
  • 각 후보 숫자를 만드는 데 필요한 자릿수가 입력에 충분히 있는지 확인한다.
  • 조건을 만족하는 후보가 하나라도 있으면, 나머지 자릿수를 앞에 배치해 8의 배수를 완성할 수 있으므로 참을 반환한다.

자릿수가 3개 미만인 경우

자릿수가 세 개보다 적으면 가능한 순열의 수가 매우 제한적입니다. 원래 순서와 뒤집은 순서 두 가지만 확인하면 됩니다.

  • input_num을 정수로 변환해 8로 나눈 나머지가 0이면 참을 반환한다.
  • 그렇지 않으면 input_num을 뒤집은 뒤 다시 검사하고, 나누어 떨어지면 참을 반환한다.
  • 둘 다 아니면 거짓을 반환한다.

알고리즘 단계

  1. 길이가 3 미만이면 위 방법으로 직접 확인한다.
  2. 크기가 10인 배열(temp_arr)을 0으로 초기화하고, 입력의 각 자릿수 등장 횟수를 센다.
  3. count를 104부터 999까지 8씩 증가시키며 반복한다.
    • temp에 count를 저장하고, 크기 10의 occurences 배열을 0으로 초기화한다.
    • temp의 각 자릿수를 추출해 occurences에 기록한다(세 자리이므로 세 번 반복).
    • 후보에 필요한 각 자릿수의 개수가 temp_arr의 사용 가능한 개수를 초과하면 다음 후보로 넘어간다.
    • 모든 자릿수가 충분하면 참을 반환한다.
  4. 반복이 끝날 때까지 만족하는 후보가 없으면 거짓을 반환한다.

자릿수 빈도 계산에 O(n), 세 자리 후보 검사는 최대 약 112개의 상수 시간 작업이므로 전체 시간 복잡도는 O(n)입니다. 자릿수가 수천 개인 매우 큰 숫자도 효율적으로 처리할 수 있습니다.

구현 예제

def solve(input_num):
    n = len(input_num)

    # 자릿수가 3개 미만이면 직접 확인
    if n < 3:
        if int(input_num) % 8 == 0:
            return True
        input_num = input_num[::-1]
        if int(input_num) % 8 == 0:
            return True
        return False

    # 각 자릿수(0~9)의 등장 횟수 계산
    temp_arr = [0] * 10
    for ch in input_num:
        temp_arr[int(ch)] += 1

    # 세 자리 8의 배수(104 ~ 992)를 모두 검사
    for count in range(104, 1000, 8):
        # 후보 숫자의 자릿수 빈도 계산
        temp = count
        occurences = [0] * 10
        for _ in range(3):
            occurences[temp % 10] += 1
            temp //= 10

        # 필요한 자릿수가 입력에 충분한지 확인
        temp = count
        possible = True
        for _ in range(3):
            d = temp % 10
            if occurences[d] > temp_arr[d]:
                possible = False
                break
            temp //= 10

        if possible:
            return True

    return False


if solve("4696984"):
    print("Divisible by eight")
else:
    print("Not divisible by eight")

입력

4696984

출력

Divisible by eight

위 예제에서 4696984에는 자릿수 9, 8, 4가 포함되어 있고, 984 = 8 × 123이므로 8의 배수를 만들 수 있습니다. 따라서 "Divisible by eight"가 출력됩니다. 반면 조건을 만족하는 세 자리 조합이 존재하지 않는 숫자라면 "Not divisible by eight"가 출력됩니다.