[프로그래머스] 기사단원의 무기 파이썬 알고리즘 문제풀이 (약수의 개수 구하기)

안녕하세요. 은공지능 공작소의 파이찬입니다.
오늘은 level 1 "기사단원의 무기" 문제 풀어보겠습니다.
효율적으로 약수의 개수를 구하는 방법이 중요한 문제입니다.

 

 

 

 

 

해당 문제 바로가기 링크 ↓↓↓

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

프로그래머스

 

 

 

 

 

1. 약수의 개수 구하는 함수 만들기

---

def get_cds(n, limit , power):
    cnt = 0
    for i in range(1, int(n**(1/2))+1): # ★포인트1. 제곱근만큼만 반복
        if n%i == 0:
            if i == n//i: # 제곱근일 경우 -> 1개만 카운트하기
                cnt += 1
            else:
                cnt += 2 # 제곱근이 아닐 경우, 2개 카운트 (i, n//i)
        if cnt > limit:  # ★포인트2. 소수의 개수가 limit를 넘어가면
            return power #            강제로 power만큼을 return 
    return cnt

약수의 개수를 구하는 함수에서 중요한 포인트는 2가지 입니다.

첫번째로, for문을 돌릴 때, int(제곱근)까지만 반복하는 것 입니다.
예를 들어, 18의 제곱근은 4.xxx정도가 나옵니다.
for문을 돌리면 1, 2, 3, 4가 각각 18의 약수인지를 볼 것입니다.
[1, 2, 3]이 각각 카운트되고, 18을 각각의 약수들로 나눈 [18, 9, 6]도 카운트 됩니다.

18의 제곱근 이상 반복하는 것은 의미가 없습니다.
반복문이 돌아 6이 나온다고 해도, 이미 약수에 추가가 되어 있기 때문입니다.
여기서 6을 추가하면, 중복카운트 이므로 정답이 아니게 됩니다.

두 번째 포인트는, 문제의 제한조건을 활용하는 것입니다.
문제에서, 약수의 개수가 특정 숫자를 넘어가면,
강제로 power만큼으로 고정하라는 조건이 나옵니다.

※
제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는
협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다.
※

그렇기에 cnt의 개수가 limit을 넘어가면
for문이 더 돌 필요도 없이, 강제로 power를 리턴하고 종료하는 것입니다.
limit과 power는 get_cds의 파라미터로 받았습니다.

반응형

 

 

 

 

2.  전체 정답 공개

---

def get_cds(n, limit , power):
    cnt = 0
    for i in range(1, int(n**(1/2))+1): # ★포인트1. 제곱근만큼만 반복
        if n%i == 0:
            if i == n//i: # 제곱근일 경우 -> 1개만 카운트하기
                cnt += 1
            else:
                cnt += 2 # 제곱근이 아닐 경우, 2개 카운트 (i, n//i)
        if cnt > limit:  # ★포인트2. 소수의 개수가 limit를 넘어가면
            return power #            강제로 power만큼을 return 
    return cnt

    
def solution(number, limit, power):
    total = 1
    for i in range(2, number+1):
        len_cds = get_cds(i, limit, power)
        total += len_cds

    return total

solution 부분은 단순히 약수들의 개수를 합산해주는 부분이라,
보고 이해하시기 어렵지 않으실 것 입니다.
도움이 되셨다면 하단의 하트 부탁드립니다! 

모두 코딩테스트를 통과하는 그날까지 화이팅!