Algorithm/프로그래머스

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

potato_pizza 2024. 5. 1. 17:14
728x90

Programmers

기사단원의 무기

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제

코드

  • 시간 초과 코드
  • 약수의 개수를 구할 때 단순하게 접근하면 시간 초과가 발생함.
def solution(number, limit, power):
    answer = 0
    lst = []
    for i in range(1, number+1):
        count = 0
        for j in range(1, i+1):
            if i % j == 0:
                count += 1
        lst.append(count)

    for k in lst:
        if k > limit:
            answer += power
        else:
            answer += k
    return answer
  • 시간 초과를 해결하기 위해서는 약수를 찾을 때 해당하는 수의 제곱근까지만 찾으면 되는 개념을 활용해야함.
  • 예를 들어, 36의 약수는 [1,2,3,4,9,12,18,36] 으로 구성되어 있음. 1-36, 2-18, 3-12, 4-9가 쌍을 이룰 수 있는 것을 알 수 있음.

 

  • 수정된 코드
def solution(number, limit, power):
    answer = 0
    lst = []

    for n in range(1, number+1):
        count = 0
        for i in range(1, int(n**0.5) + 1):
            if n % i == 0:
                if i == (n // i):
                    count += 1
                else:
                    count += 2
        lst.append(count)

    for k in lst:
        if k > limit:
            answer += power
        else:
            answer += k
    return answer

 

  • 만약 제곱근 값 * 제곱근 값으로 해당 수가 만들어진다면 약수를 count할 때 +1만하고 그 외의 경우에는 쌍을 이루기 때문에 count +2를 해주면 됨. 
728x90
반응형