[프로그래머스/파이썬] 기사단원의 무기 풀이

🔗 문제 링크

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

프로그래머스

  프로그래머스의 Level 1 연습문제로 문제 자체가 엄청 복잡한 편은 아니지만 약수의 개수를 구하는 과정이 포함되어 있기에, 이를 정리하기 위해 해당 문제에 대한 풀이를 작성하고자 한다!

 

 

---

🔎 문제 풀이 & 작성 코드

  문제에서 주어진 기사단원의 수 number에 대해 1~number의 숫자들의 약수의 개수를 모두 구한다. 그다음 각 기사단원은 약수의 개수만큼의 공격력을 가진 무기를 갖게 되는데 약수의 개수가 limit이라는 정수보다 큰 경우에는 지정된 power라는 크기의 무기를 가져야 한다. 이 문제에서의 핵심은 약수의 개수를 구하는 것!!

 

  파이썬 코드로 약수의 개수를 구하는 방법은 다양하게 있다. 처음에는 단순히 숫자가 주어졌을 때, 1부터 해당 숫자까지 모두 살펴보며 약수의 개수를 구했더니 시간초과가 발생하였다. 그래서 조금 더 수학적으로 접근하여 약수의 개수를 구했다. (아래의 내용은 프로그래머스의 질문하기의 답변을 일부 참고 하였음)

 

1) 내가 사용한 방법 - N의 제곱근으로 범위를 좁혀 탐색하기 

  N = 12일때, 12의 약수는 1,2,3,4,6,12이다. 12의 제곱근은 약 3.45이다. 이때, 1부터 3까지 탐색하게 된다면, 1*12, 2*6, 3*4로 모든 약수의 쌍을 구할 수 있다. 이런 방식에서는 만약 주어진 숫자가 제곱수라면 예외가 발생한다. N = 16일 때, 16의 제곱근은 4이고 1부터 4까지 탐색하게 되면 1*16, 2*8, 4*4의 세 쌍을 모두 구할 수 있지만 4*4의 쌍에서의 실질적인 약수는 4 하나이다. 그래서 이런 중복을 줄이기 위해서는, 제곱근까지 탐색하는 과정에서 N = n*n의 조건을 만족하면 약수를 1개만 구하거나, 이 방식을 통해 찾은 모든 숫자 쌍의 각 숫자들을 리스트에 저장한 후 set 등을 사용하여 중복을 제거해 주면 된다. 이 방식을 사용해 내가 직접 작성한 코드는 다음과 같다.

fe = [0]*100001 # 약수의 갯수를 저장해두기 위해 선언한 리스트

def prime_num(n): # 약수의 갯수를 구하는 함수
    num = 0
    for i in range(1,int(n**0.5)+1):
        if n/i == i:
            num+=1
        elif n%i == 0:
            num+=2
            
    return num

def solution(number, limit, power):
    answer = 0
    for x in range(1, number+1):
        if fe[x] == 0:
            fe[x] = prime_num(x)

        if fe[x] > limit:
            answer+=power
        else:
            answer+=fe[x]
        
    return answer

 

2) 소인수분해를 통해 약수의 개수 구하기

  약수의 갯수만 구하면 된다면, 소인수 분해를 활용해도 된다. 소인수 분해를 통해 우리는 숫자를 소수들의 곱으로 나타낼 수 있다. 이때, 소수들의 지수에다가 1을 더한 값들을 모두 곱하면 약수의 개수를 구할 수 있다. 숫자가 12일 때, 이 숫자는 인수분해를 통해서는 2^2+3^1로 표현할 수 있다. 이때 (2+1)*(1+1) = 6으로 약수의 개수를 구할 수 있다. 하지만 소인수분해를 코드로 구현하는 것은 위의 방식보다는 비효율적이다!! 

 

 

 

 

---

🌍 깃허브 링크

실제 작성한 해당 정답 코드는 깃허브에도 업로드해두었습니다.

dohyun-99 - Overview