[Programmers] 기사단원의 무기

문제 설명

---

문제 풀이 과정

문제가 쉽다고 생각했다. 사실 약수는 해당 수를 1부터 해당 수까지 나눠서 나머지가 없어야 하는 것으로 하는 건데 문제는 이중 for문을 쓰면 복잡도가 올라가서 실행 시간이 초과된다... 그래서 실패

def solution(number, limit, power):
    answer = 0
    for i in range(1, number+1):
        count = 0
        for j in range(1, i+1):
            if i % j == 0:
                count += 1
        if count <= limit:
            answer += count
        else:
            answer += power
    return answer

다른 사람의 풀이

인터넷에서 나온 다른 사람의 풀이

def divisor(n):
    a = []
    for i in range(1, int(n ** 0.5)+1):
        if n % i == 0:
            a.append(n//i)
            a.append(i)
    return len(set(a))

def solution(number, limit, power):
    answer = 0
    for i in range(1, number+1):
        a = divisor(i)
        if a > limit:
            answer += power
        else:
            answer += a
    return answer

 

1. 사실상 해당 숫자의 약수 중 최대 값은 해당 숫자 제외 제곱근인 것을 이용.
2. 해당 숫자에서 제곱근까지의 숫자를 나눠서 계산을 줄였다.
3. divisor에서 append를 i와 n//i 를 하는 것은 결국 나눠질 때 몫도 약수이기 때문에 같이 진행
4. set을 통해 중복 제거

항상 약수는 시간 초과 때문에 실패하는 것 같다. 제곱근 사용해서 하는 것 잊지 않기.

- coding test url:

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

프로그래머스