[programmers lv1.python] 기사단원의 무기 풀이

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

프로그래머스

문제

---

1차 풀이(❌)

def solution(number, limit, power):
    divisors = []
    for i in range(1, number + 1):
        count = 0
        for j in range(1, i + 1):
            if i % j == 0:
                count += 1
        divisors.append(count)
        
    for j in range(len(divisors)):
        if divisors[j] > limit:
            divisors[j] = power
    return sum(divisors)

 

첫 번째 for문에서는 number를 순회하면서 약수가 구해질 때 마다 갯수를 count 하기 위해 변수를 할당해준 후 1씩 갱신해서 divisors 리스트에 붙여주고, 두 번째 for문에서는 divisors 리스트를 순회하면서 리스트의 요소가 limit 보다 크다면 해당 요소를 power로 대체하도록 코드를 짜줬다.

 

테스트는 무난히 통과했으나 코드를 제출해보니 우수수 시간초과가 났다 ㅠ

제한사항으로 number의 범위가 1 <= number <= 100,000 인데, 이것까지 생각을 못해서 모든 수의 약수를 구하는 과정에서 시간 초과가 나는 것 같았다.

 

약수를 구하는 과정의 시간을 좀 더 단축시킬 순 없을까? 를 고민하다가 방법을 조금만 틀어서 구해보기로 했다. 이 문제는 '약수가 뭔지'를 구하는 것이 아니라 '약수의 개수'를 구하는 것이기 때문에 !!

---

2차 풀이(⭕)

def solution(number, limit, power):
    divisor_count = [0] * (number + 1)
    
    for i in range(1, number + 1):
        for j in range(i, number + 1, i):
            divisor_count[j] += 1
            
    for idx in range(1, number + 1):
        if divisor_count[idx] > limit:
            divisor_count[idx] = power
            
    return sum(divisor_count)

 

두 번째 for문의 로직은 동일하고, 1차 풀이와 달라진 것은 첫 번째 for문에서 약수의 갯수를 구하는 로직이다. 1차에서처럼 각 수를 나눠가면서 나누어 떨어지는 것을 찾는 게 아니라, 배수의 자리를 찾음으로써 시간을 대폭 줄일 수 있었다.

 

자세한 설명

number가 10이라고 가정해보자.

1. 처음에는 divisor_count 리스트를 모두 0으로 초기화한다.
   • divisor_count = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
2. i가 1일 때:
   • 1의 배수는 모든 수이므로, divisor_count 리스트의 모든 값에 1씩 더한다.
     • divisor_count = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
3. i가 2일 때:
   • 2의 배수는 2, 4, 6, 8, 10 이다. 이들 인덱스에 해당하는 divisor_count 값을 1씩 증가시킨다.
     • divisor_count = [1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1]
4. i가 3일 때:
   • 3의 배수는 3, 6, 9 다. 이들 인덱스에 해당하는 divisor_count 값을 1씩 증가시킨다.
     • divisor_count = [1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1]
5. i가 4일 때:
   • 4의 배수는 4, 8 이다. 이들 인덱스에 해당하는 divisor_count 값을 1씩 증가시킨다.
     • divisor_count = [1, 2, 2, 3, 1, 2, 1, 3, 2, 2, 1]
6. 나머지 i 값에 대해서도 위와 같은 과정을 반복하면 최종 값이 약수의 갯수가 된다.

시간초과도 없고 시간도 대폭 줄여서 성공! 🥹

---

마치며

안 풀릴 땐 다른 길을 생각해보자. 시간초과가 나는 덴 이유가 있음 .. 해결할 수 있는 방법도 반드시 있음 ..