[프로그래머스] 연습문제 - 기사단원의 무기

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/136798

프로그래머스

 

2. 풀이

1. 1부터 주어진 수까지 반복문을 돌며 각 수의 약수 개수 count를 구한다.

2. 해당 수의 약수 개수 count 가 limit보다 클 경우(초과), 개수를 power로 변경한다.

3. count를 divisor_list에 넣고 총 합을 리턴한다. 

 

3. 초기 작성 코드 (실패)

def solution(number, limit, power):
    answer = [1]
    
    for i in range(2, number+1):
        count = 2 # 1, 자기 자신
        if i > 3:
            for j in range(2, int(i/2)+1):
                if i % j == 0:
                    count += 1
        if count>limit:
            count = power
            
        answer.append(count)
    
    return sum(answer)

 

 

수많은 시간 초과의 향연...... 또르르...

 

4. 개선된 코드 (성공) 

이전 코드에서 시간 초과 판정이 난 것을 감안해서, 연산 횟수를 줄이기 위해 2가지 Point를 개선했습니다.

 

개선점1 

As-is

기존에는 해당 수의 약수를 구하기 위해서 주어진 수의 반절 지점까지(1/2) 확인하고 약수 판별을 진행했는데요.

 

To-be

사실 약수를 구할 때에는  주어진 수의 제곱근까지만 확인하면 된다는 점을 이용해서 연산 수를 줄였습니다.

 

자연수 n의 약수가 x라면, n/x = y 역시 n의 약수인데요. 이와 같이 자연수 n은 약수 간의 곱으로 이루어져 있으므로, 하나의 약수를 알게 되면 다른 약수 또한 구할 수 있게 됩니다. 

 

수학적 증명은 아래 블로그 참고!

https://doodle-ns.tistory.com/32

[노트] 모든 약수를 구하는 알고리즘은 O(sqrt(n))이다.

 

이 점을 이용해서 약수의 개수를 구하는 코드를 짜게 되면 문제점이 하나 생기는데, 바로 9, 16, 25와 같이 같은 수의 제곱으로 이루어진 수들의 경우 중복 카운트가 된다는 것인데 해당 부분도 처리해주는 코드를 작성했습니다.

같은 수의 제곱으로 이루어지지 않은 경우에만(10 line) 추가로 count를 +1 해줌으로써 2*8과 같이 다른 수로 이루어진 경우 작은 약수와 큰 약수를 한 번에 카운트하고, 4*4와 같이 같은 수의 제곱으로 이루어진 경우에는 한 개의 수만 카운트하게 됩니다. 

 

개선점2

As-is

기존에는 약수를 카운트하는 반복문 로직이 종료된 후, 약수의 개수가 limit보다 클 경우 power로 바꿔주는 코드였는데요.

 

To-be

불필요한 연산 횟수를 좀 더 줄이기 위해서 반복문 내에 count가 limit보다 클 경우 바로 count를 power로 바꾸고 약수를 구하는 반복문을 종료하도록 하는 코드를 추가했습니다. 

 

def solution(number, limit, power):
    answer = [1]
    
    for i in range(2, number+1):
        count = 2 # 1, 자기 자신
        
        for j in range(2, int(i**0.5)+1): # 개선점 1 적용
            if i % j == 0:
                count += 1
                if j*j != i: # 개선점 1 적용 (중복 처리)
                    count+=1
        	
            if count>limit: # 개선점 2 적용
                count = power
                break
            
        answer.append(count)
        
    return sum(answer)

 

 

완료!