기사단원의 무기

문제 설명

 

제한사항, 입출력 예 및 설명

문제 풀이

def solution(number, limit, power):
    answer = 0
    cnt_list = []
    
    for n in range(1, number+1):
        set1 = set()
        i = 1
        # 약수 구하기
        while True:
            res = n % i
            if res == 0:
                set1.add(i)
                set1.add(n//i)
            i += 1
            if i in set1:
                break
            if i > n :
                break
        # 약수 개수 구하기
        cnt = len(set1)
        cnt_list.append(cnt)
    # 약수 개수가 limit을 초과하면 power로 바꿔주기
    for i, c in enumerate(cnt_list):
        if c > limit:
            cnt_list[i] = power
    
    # 최종 약수 개수를 다 더해서 필요한 철의 무게 구하기
    answer = sum(cnt_list)
    return answer

채점 결과

시간초과로 인한 실패

 

---

문제 풀이2

import math
def solution(number, limit, power):
    answer = 0
    cnt_list = []
    for n in range(1, number+1):
        cnt = 0
        if n == 1:
            cnt += 1
        elif n == 2:
            cnt += 2
        else:
            for i in range(1, int(math.sqrt(n)+1)):
                
                res = n % i
                if res == 0:
                    if i == n//i:
                        cnt += 1
                    else:
                        cnt += 2
        cnt_list.append(cnt)
    for i, c in enumerate(cnt_list):
        if c > limit:
            cnt_list[i] = power
            
    answer = sum(cnt_list)
    return answer
    
    
    
    
==============================================================================    
import math
def solution(number, limit, power):
    answer = 0
    cnt_list = []
    for n in range(1, number+1):
        cnt = 0
        # if n == 1:
        #     cnt += 1
        # elif n == 2:
        #     cnt += 2
        # else:
        for i in range(1, int(math.sqrt(n)+1)):

            res = n % i
            if res == 0:
                if i == n//i:
                    cnt += 1
                else:
                    cnt += 2
        cnt_list.append(cnt)
    for i, c in enumerate(cnt_list):
        if c > limit:
            cnt_list[i] = power
            
    answer = sum(cnt_list)
    return answer

숫자 1과 2는 약수가 1, 2개 있는 것이 명확하기 때문에 for문으로 돌지 않고, 바로 cnt에 더해줌.원래는 for문으로 같이 돌면서 약수 구해주려고 했는데 코드가 잘 안 짜졌음...ㅎㅎ (최종 코드에서는 해당 부분은 없어도 됨)

 

모든 수를 다 돌면서 약수인지를 확인할 필요가 없다. 문제 풀이1에서는 약수를 list에 다 저장해놓고, i로 n을 나눈 몫이 약수 list에 있을 경우 break 를 하는 방식으로 풀었다. 근데 그것보다 더 좋은 방법이 있다. n의 제곱근을 활용하는 것이다. n의 제곱근의 상수부분까지만 for문이 돌면된다. 예를 들어서 n=4인 경우, 4의 제곱근은 2인데, for i in range(1, 2) 까지 하면 i가 1만 가질 수 있으니까 제곱근+1 까지 돌아야 한다. 그러니까 for i in range(1, 제곱근+1) 이렇게. 그럼 n=6일 땐? 즉, 6의 제곱근이 소숫점을 가질 때는?? 6의 제곱근은 2 < 6의 제곱근 < 3 이기 때문에 2.xxx 일 것이다. 6에서는 1x6, 2x3 을 잡아내야하기 때문에 2까지는 돌아야한다. 때문에 int(2.xxx + 1)를 하면 된다. 이렇게 해야 n의 제곱근이 정수일 때, 소숫점을 가질 때를 동시에 코딩할 수 있다. 

 

그리고, n=4일 때처럼 약수가 2일 때 몫도 2이기 때문에 1,2,2,4가 되는데. 2는 중복이라서 4의 약수는 1,2,4 이렇게 3개가 된다. 이런 중복을 걸러내기 위해서 res(몫) = n//i 을 저장하고, 만약에 i랑 res랑 같은 경우에(4를 2라는 i로 나눴을 때 2라는 res가 나온 경우) cnt에는 +2 가 아니라 +1을 해주었다.

 

해당 n에 대한 약수 cnt를 다 따졌으면, cnt_list에 append를 해주고 다음 n의 약수를 구한다.

 

첫 번째 for문을 다 돌면, 모든 n에 대한 약수 cnt가 cnt_list에 append가 되어 있을 것이고, 두 번째 for문을 돌면서 cnt_list에서 limit을 초과하는 수가 있으면 power로 바꿔준다.

 

두 번째 for문을 다 돈 후에, cnt_list에 있는 값들을 더해서 무기를 만드는데 필요한 철의 총 무게를 구해준다. 

채점 결과2

---

다른 사람 풀이

def solution(number, limit, power):
    answer = 0 
    for i in range(1, number + 1):
        count = 0
        for j in range(1, int(i ** 0.5) + 1):
            if i % j == 0:
                count += 1
                if i // j != j:
                    count += 1

            if count > limit:  # 애초에 limit을 넘어가는 count는 소용이 없기 때문에 count가 limit을 넘어가면 break
                break

        if count > limit:
            answer += power
        else:
            answer += count



    return answer

다른 사람 풀이 채점 결과

내 풀이와 속도는 비슷한 것 같다. 

 

문제 출처 : 프로그래머스 / 기사단원의 무기 (약수 구하기, 루트, sqrt, **0.5)