프로그래머스 알고리즘 Lv4 숫자 블록

문제출처 https://programmers.co.kr/learn/courses/30/lessons/12923

문제를 읽어보면 그냥 순서대로 구현하기 자체는 매우 쉽다. 그러나, 길이가 최대 1,000,000,000에 달하기 때문에 주먹구구식으로 코드를 짰다가는 결과값을 보는 것 자체가 불가능할 정도로 굉장히 오래 걸린다.

이 사이트 문제가 항상 그러하지만 이번에는 더욱더 효율적인 해법이 중요시되는 문제인듯하다.

내 해법의 접근과정을 풀어보자면,

① 다 풀어놓고 주어진 범위를 가져오는 것이 아닌, begin과 end 사이의 값만 계산해서 도출. (매우 당연하다.)

② 숫자 몇 개를 늘어놓고 직접 해보면 알겠지만 주어진 인덱스를(begin, end 사이 값)을 2부터 시작해서 딱 나눠지면 그 나눈 값이 그 인덱스의 값이다.

③ 2부터 나눠보기 때문에 begin==1 인 경우는 직접 추가. (1을 나누어 떨어뜨릴 수 있는 것은 1뿐이다.)

여기까지만 구현했더니 정답 자체는 모두 맞출 수 있었다. 하지만, 효율성 테스트를 통과하지 못해서 코드를 이리저리 굴려보다가 문득 찾아낸 것은,

④ 소수의 경우는 1과 자신으로 나뉘기 때문에 2부터 나눠보기 시작하는 반복문을 굉장히 많이 낭비한다. 소수의 경우는 바로 1로 처리한다.

n이 소수인지 판별을 어떻게 할까? 1 이외 n의 제곱근이하의 정수 중 아무 것으로도 나누어 떨어지지 않으면 n은 소수다!

그래서 생긴 코드

from math import sqrt
 
def solution(begin, end):
    result=[]
    if begin==1:
        result.append(0)
        begin+=1
    for i in range(begin,end+1):
        for j in range(2,int(sqrt(end)+1)):            
            if i%j==0:
                result.append(i//j)
                break
        else : result.append(1)
 
    return result