https://programmers.co.kr/learn/courses/30/lessons/12923

어제 파이썬 질문글 올라온거 해보려는데

정확성은 다 통과하고 왜 효율성에서 다 틀리냐 ㅇㅅㅇ...


# 코드 설명

# 문제에 따르면 소인수분해하여 나온 값들중

# 최소값을 뺀 나머지를 모두 곱한 값이

# 그 위치의 최대값이다.

# 짝수일 경우 최소값은 2이므로

# 위치의 절반(한비트 우측으로 이동)이 최소이다.


from functools import reduce

from operator import mul

from math import sqrt, ceil


def odd_prime_factorization(odd):

    # 소인수 분해할 숫자가 홀수 라는것을 알고있으므로

    # 검사하지 않고 바로 들어가는 함수를 만든다.

    # 이때 1은 최소값을 제외하는데 방해되는 값이기 때문에 밑에서 처리해준다.

    for i in range(3, ceil(sqrt(odd)) + 1, 2):

        if odd % i == 0:

            return odd_prime_factorization(odd // i) + [i]

    return [odd] # odd가 소수일 경우 이곳을 통해 값이 전달되어 나온다.


def odd_max_factor(odd):

    odd_prime_factors = odd_prime_factorization(odd)

    odd_prime_factors.remove(min(odd_prime_factors)) # 약수들 중 최소값 제거

    if odd_prime_factors:

        return reduce(mul, odd_prime_factors) # odd를 제외한 최대 약수반환

    return 1 # 리스트 크기가 1일때 odd를 제외하면 1이외의 약수가 없다는 의미가 된다.


def solution(begin, end):

    # 리스트 초기화, 짝수값을 미리 넣어둔다.

    answer = [i >> 1 for i in range(begin, end + 1)]

    if begin & 1:

        # begin이 홀수일 때

        for i in range(0, len(answer), 2):

            answer[i] = odd_max_factor((answer[i] << 1) + 1)

        if begin == 1:

            answer[0] = 0

        return answer

    # begin이 짝수일 때

    for i in range(1, len(answer), 2):

        answer[i] = odd_max_factor((answer[i] << 1) + 1)

    return answer