[Programmers] Level 2. 숫자 블록

🔗 Problem Link

프로그래머스

---

❔Thinking

• begin, end가 주어질 때, 해당 구간에 놓이는 숫자 블록을 반환한다.
• 숫자 블록은 n*2, n*3, n*4 순서로 놓인다
  • n = 1인 경우, [0,1,1,1,1,1,1,1,1]
  • n = 2인 경우, [0,1,1,1,2,1,2,2,1]
  • n = 3인 경우, [0,1,1,1,2,1,3,2,1]
• 1 <= begin <= end <= 1,000,000,000
• 블록에 적힌 숫자 <= 10,000,000

---

💻Solution

from bisect import bisect_left

def find_divisors(n)->list:
    divisor_list = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisor_list.append(i)
            if i**2 != n:
                divisor_list.append((n // i))
    divisor_list.sort(reverse=True)
    return divisor_list

def solution(begin, end):
    answer = []
    for num in range(begin, end+1):
        if num == 1:
            answer.append(0)
            continue
        div_list = find_divisors(num)
        for i in div_list:
            if i * 2 <= num and i <= 10**7:
                answer.append(i)
                break
    return answer

---

🗝️keypoint

1. 해당 위치에 놓이는 숫자블록은, 해당 위치보다 작은 가장 큰 숫자이다. 즉 큰 수부터 확인하여 범위에 해당한다면 탐색을 멈춘다. ( = bisect_left)
2. 숫자의 범위가 10,000,000이므로, 이 숫자를 넘는 블록은 놓일 수 없다.
3. 약수의 개수를 구하는 방법은, 제곱수까지만 구하는 방법을 통해 최적화 할 수 있다. (단, 9와 같은 제곱수인 경우 3이 중복되지 않도록 주의한다.)