[연습문제 / 프로그래머스] 12923번 : 숫자 블록(다시)

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12923

 

Lv2 문제다!

 

문제 이해

예제를 자세히 보니 약수관련 문제라고 생각했다.

소수 인덱스에서는 값이 모두 1이고, 합성수 인덱스에서는 자기보다 작은 약수 중 최대 약수가 값이었다.

그래서 begin에서 end까지 진행하면서 소수인지 합성수인지에 따라 분기문을 다르게 해서 진행하면 되겠다 싶었다. 

 

풀이 이해 

 

• 합성수에서 가장 큰 약수는 (합성수 // 가장 작은 약수)의 값이다.
• 그래서 작은 수부터 순차적으로 가다가 약수이고, 그 수로 나눈 몫이 1000만 이하인 수일 때의 값을 k에 저장한 뒤 j 반복문을 break 한다. (이러면 시간을 많이 아낄 수 있다)
• 1000만 이하인 걸 확인해야하는 이유 : 숫자 블럭의 최대는 1000만이지만 도로의 최대는 10억이기 때문이다
• 위의 과정을 거치지 않았다면 소수나 1인 경우이므로 따로 소수인 경우를 처리하지 않아도 된다.
• k값을 answer에 추가한 뒤 결과를 반환한다

 

- 정답 풀이 

 

참고한 블로그

import math

def solution(begin, end):
    answer = []
    for i in range(begin, end + 1):
        if i == 1:
            k = 0
        else:
            k = 1
        for j in range(2, int(math.sqrt(i)) + 1):
            if i % j == 0 and i // j <= 10000000:
                k = i // j
                break
        answer.append(k)
        
        
    return answer

 

- 시도해본 풀이 

문제 이해한 걸로 풀이를 작성했다.

정확성에서는 다 맞았는데, 효율성에서는 모두 통과하지 못했다.

아무래도 end가 최대 10억인 수라서 아래 연산으로는 시간이 많이 걸리는 것 같다 

효율성에서 시간초과는 이해하는데 실패는 어떤 의미일까?? 

 

import math

def isPrime(num):
    if num == 1:
        return False
    
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
        
    return True

def findFactor(num):
    factor = 0
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0 and num // i <= 10000000:
            factor = num // i
            break
    
    return factor

def solution(begin, end):
    # 소수는 약수가 없으므로 무조건 1, 합성수는 자기보다 작은 최대 약수 
    answer = [0] * (end - begin + 1)
    
    for i in range(begin, end + 1):
        if isPrime(i):
            answer[i - begin] = 1
            
        else:
            answer[i - begin] = findFactor(i)

    return answer