사용 언어 - 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
레퍼런스
- 정답 참고
- 정답 깃허브
'Algorithm > 구현' 카테고리의 다른 글
[프로그래머스 lv1] 푸드 파이트 대회 (1) | 2023.05.09 |
---|---|
[프로그래머스 lv1] 과일 장수 (0) | 2023.04.26 |
[프로그래머스 lv1] 명예의 전당 (0) | 2023.04.25 |
[프로그래머스 lv1] 문자열 나누기 (0) | 2023.04.25 |
[프로그래머스 lv1] 가장 가까운 같은 글자 (0) | 2023.04.25 |
댓글