[프로그래머스 lv1] 기사단원의 무기

사용 언어 - Python3

문제 - 기사단원의 무기

프로그래머스

 

 

정답

약수 시간초과 없이 구하기 (정답 맞춘 여부 X)

약수를 구하는 과정에서 이중 for문으로 인해 시간초과가 뜬다.

# 시간초과
def solution(number, limit, power):
    # number 안의 약수 개수 = 공격력 무기
    num = []
    for i in range(1,number+1):
        cnt = 0
        for j in range(1,i+1):
            if i % j == 0:
                cnt += 1
        num.append(cnt)
    
    for i in range(len(num)): # 공격력이 limit 초과한 경우 power
        if num[i] > limit :
            num[i] = power
            
    return sum(num)

 

시간초과 없이 구하려면, j의 범위를 제곱근까지만 설정해야한다.

예) 6의 약수는 1,2,3,6

1부터 6까지 전부 나눠서 구하지 말고, 6의 제곱근까지만 나눠준다. 1,2까지만!

6/1 -> 나누어떨어짐. cnt += 1

6/2 -> 나누어떨어짐. cnt += 1

j**2 == i인 경우, 9의 약수인 1,3,9인 경우 3은 제곱시 9이기 때문에 또 약수개수를 추가하면 안된다.

약수가 홀수개수로 떨어지는 경우를 제외하기 위해 조건을 건다.

j**2 != i인 경우, 약수가 짝수개수인 경우, 각 j마다 cnt+=1을 해준다.

1**2 != 6 -> 조건만족. cnt += 1

2**2 != 6 -> 조건만족. cnt += 1

def solution(number, limit, power):
    # number 안의 약수 개수 = 공격력 무기
    num = []
    for i in range(1,number+1):
        cnt = 0
        for j in range(1,int(i**(1/2)+1)):
            if i % j == 0:
                cnt += 1
                if j**2 != i:
                    cnt += 1
        num.append(cnt)
    
    answer = 0
    for i in range(len(num)): # 공격력이 limit 초과한 경우 power
        if num[i] > limit :
            num[i] = power
        answer += num[i]
            
    return answer

 

 

레퍼런스

• 정답 참고

[프로그래머스] Lv 1 기사단원의 무기 - Python

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부