[프로그래머스] 숫자 블록 (파이썬)

난이도 : LV 2

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12923#

문제해결 아이디어

• 평범한 소수 판별문제인줄 알았지만 조건을 잘 충족시키는것도 쉽진않았다.
• 테스트케이스 13번이 틀려서 질문하기 게시판의 반례를 참고했다.
• 예시 케이스로 [begin, end] = [100000014, 100000016] 를 테스트했을 때, [1, 1, 6250001]이 아닌 [6, 5, 6250001]이 출력되어야 합니다.
• 몫이 10**7을 넘어가면 무시하는 것이 아닌 나눴던 수를 포함시키는것이 포인트였다.

소스코드

def sosu(n):
    if n == 1:
        return 0
    ans=[]
    for i in range(2, int(n ** 0.5)+1):
        if n % i == 0:
            if n//i <= 10000000:
                ans.append(n//i)
                break # 몫이 10**7 이하 조건을 만족하면 가장먼저 나온수가 제일 크므로 더이상 순회할필요가 없다.
            else:
                ans.append(i)
            
    return max(ans) if ans else 1

def solution(begin, end):
    ans = []    
    for i in range(begin,end+1):
        ans.append(sosu(i))
    return ans