시간 복잡도를 줄이기 위한 소수 구하기, 약수 구하기 (Python)

프로그래머스 level1. 소수찾기 

 

원래 풀이대로 하면 시간 초과가 되었다. n의 조건이 2<= n <= 1000000이므로 이 문제는 에라토스테네스의 체를 이용하여 구해야 한다. 

풀이방법:

def solution(n):
    answer = 0
    #에라토스테네스의 체 
    a = [False, False] + [True]*(n-1)   #0,1을 제외한 모든 수를 소수라고 지정 
    primes = []
    
    for i in range(2, n+1):
        if a[i] == True:
            primes.append(i)
            answer += 1
            for j in range(2*i, n+1, i):     #i의 배수 모두 삭제 
                a[j] = False
                
    return answer

 

---

프로그래머스 level1. 기사단원의 무기 (약수)

 

이 문제 또한 약수의 개수를 구하는 문제인데, 루트를 사용하여 시간 복잡도를 줄이는 방향으로 문제를 풀어줘야 한다.

def solution(number, limit, power):
    answer = 0
    prime = [0] * number
    for i in range(1, number+1):
        for j in range(1, int(i**(1/2))+1):
            if i % j == 0:
                prime[i-1] += 1
                if (j**2) != i:
                    prime[i-1] += 1
        if prime[i-1] > limit:
            prime[i-1] = power
    answer = sum(prime)
        
    return answer

 

처음으로 시간 복잡도를 활용해서 문제를 풀어야 통과가 되는 경험을 하면서 이전보다 문제를 풀이할 때 시간 복잡도를 고려한 방식으로 생각하게 되는 계기가 된 문제들이었다.