14. 기사단원의 무기 - 프로그래머스 코딩 테스트(python)

문제 설명

• 숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다.
• 각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다.
• 예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로, 공격력이 4인 무기를 구매합니다. 만약, 이웃나라와의 협약으로 정해진 공격력의 제한수치가 3이고 제한수치를 초과한 기사가 사용할 무기의 공격력이 2라면, 15번으로 지정된 기사단원은 무기점에서 공격력이 2인 무기를 구매합니다. 무기를 만들 때, 무기의 공격력 1당 1kg의 철이 필요합니다. 그래서 무기점에서 무기를 모두 만들기 위해 필요한 철의 무게를 미리 계산하려 합니다.
• 기사단원의 수를 나타내는 정수 number와 이웃나라와 협약으로 정해진 공격력의 제한수치를 나타내는 정수 limit와 제한수치를 초과한 기사가 사용할 무기의 공격력을 나타내는 정수 power가 주어졌을 때, 무기점의 주인이 무기를 모두 만들기 위해 필요한 철의 무게를 return 하는 solution 함수를 완성하시오.

제한사항

• 1 ≤ number ≤ 100,000
• 2 ≤ limit ≤ 100
• 1 ≤ power ≤ limit

number = 5
limit = 3
power = 2
# 결과는 10이 나와야 한다.
number1 = 10
limit1 = 3
power1 = 2
# 결과는 21이 나와야 한다.

def solution(number, limit, power):
    # 결과를 출력할 answer을 만든다
    answer = 0

    # number의 범위 안에 있는 모든 수의 약수를 구해야 한다.
    # range를 사용해 for문을 돌린다.
    for num in range(1,number+1):
        # 두 임의의 리스트를 만든다.
        divisors = []
        divisors_back = []

        # number까지의 범위 중 한 수인 num의 약수를 구한다.
        # 이때 num이 아주 큰 수 이면 약수를 구할때 시간복잡도가 커진다.
        # 그래서 해당 수의 제곱근의 약수를 구한다.
        for i in range(1, int(num**(1/2)) +1):
            # 만약 num범위의 수들 중 나눠서 나머지가 0이되는 수 i를
            if num % i == 0:
                # divisors에 마지막 요소로 집어 넣는다.
                divisors.append(i)
                # 이때 num을 i로 나눈 후 몫이 i랑 같지 않으면
                if i != (num//i):
                    # divisors_back에 그 몫 값을 마지막 요소로 집어 넣는다.
                    divisors_back.append(num//i)

        # 그 후 divisors와 divisors_back[::-1]을 더하면 해당 수의 약수가 된다.
        # 위 제곱근을 사용하는 방법을 아래에서 자세히 다루도록 하자.

        # 만약 divisors + divisors_back[::-1]의 길이가 limit보다 길다면
        # 즉 기사단원의 공격력이 limit보다 크다면
        if len(divisors + divisors_back[::-1]) > limit:
            # answer에 power값을 더해 주고
            answer += power
        # 그렇지 않다면
        # 즉, 기사단원의 공격력이 limit보다 같거나 작다면
        else:
            # answer에 divisors + divisors_back[::-1]의 길이 값을 더해 준다.
            answer += len(divisors + divisors_back[::-1])
    return answer

print(solution(number, limit, power))
print(solution(number1, limit1, power1))

# 10
# 21

약수 구하는 법

# 100의 약수를 구해보자.

# 약수를 구할 100을 n에 할당한다.
n = 100

# 약수를 집어넣을 divisors와 divisors_back 리스트를 만든다.
divisors = []
divisors_back = [] 

# for문을 돌려 n의 제곱근의 범위 만큼 i를 할당한다.
# 여기서 아래의 for문은 `for i in range(1, 11):` 과 같다.
for i in range(1, int(n**(1/2)) + 1):

    # i는 1,2,3,4,5,6,7,8,9,10 의 값들이 하나하나 들어간다.
    # 위 값들 중 n 즉, 100을 나눴을 때 나머지가 0이 되는 값들은
    if (n % i == 0):
        # divisors에 마지막 요소로 들어간다.
        # 여기서는 1, 2, 4, 5, 10 이 100을 나눴을 때 나머지가 0이 되므로
        # divisors에 들어갈 값은 1, 2, 4, 5, 10이다.
        divisors.append(i)

        # divisors에 들어갈 i값들 중
        # 만약 n 즉 100을 i로 나눈 후 몫의 값이 i와 같지 않다면
        if (i != (n // i)): 
            # 100을 i로 나눈 후 몫의 값을 divisors_back에 마지막 요소로 집어 넣는다.
            divisors_back.append(n//i)
        # 위 if 문을 하는 이유는
        # 만약 i값이 1, 2, 4, 5, 10중에 하나인 10이라고 가정해 보자
        # n값인 100을 10으로 나눈 후 몫의 값은 10이다.
        # 즉 i값과 n//i 값이 같은 경우이다.
        # divisors_back에 10이 들어가게 되면
        # divisors와 divisors_back 두 리스트 모두 10 값을 갖게 된다.
        # 그 후 divisors와 divisors_back[::-1]을 합하면
        # [1, 2, 4, 5, 10, 10, 20, 25, 50, 100] 처럼 10이 중복으로 들어가게 된다.
        # 이때 set으로 중복을 제거해주는 방법도 있지만
        # 이 경우에서 아예 중복되는 값을 집어넣지 않은 경우이다.

# divisors와 divisors_back[::-1]을 더하면 100의 약수들이 출력된다.
divisors + divisors_back[::-1]

# [1, 2, 4, 5, 10, 20, 25, 50, 100]

다른 사람의 풀이

# 함수 cf는 n의 약수의 개수를 출력해주는 함수이다.
def cf(n):
    
    # 리스트 a변수를 만든다.
    a = []
    
    # n의 제곱근의 범위 만큼만 for문을 돌린다.
    for i in range(1,int(n**0.5)+1):
        # n을 i로 나눈 나머지 값이 0이면
        if n%i == 0:
            # i값과 n을 i로 나눈 몫값을 a에 마지막 요소로 집어 넣는다.
            a.append(n//i)
            a.append(i)
    # 그 후 set을 사용해 a에 중복 요소를 제거한 후 그 길이를 return한다.
    return len(set(a))
 
def solution(number, limit, power):
    # if를 같이 사용한 리스트 내 for문으로 바로 return한다.
    # 1부터 number안의 정수들을 함수 cf(i)로 출력된 값만 리스트로 집어 넣는다
    # 단 limit 이하인 cf(i) 값만 그대로 집어 넣고
    # limit 초과인 cf(i)값은 cf(i)값 대신 power값을 집어넣는다.
    # 그 후 리스트 내의 모든 요소를 다 더한 값을 출력한다.
    return sum([cf(i) if cf(i)<=limit else power for i in range(1,number+1)])

print(solution(number, limit, power))
print(solution(number1, limit1, power1))

# 10
# 21