[프로그래머스] 억억단을 외우자

문제

• 1억 x 1억 크기의 억억단 행렬이 있다.
• 적당한 수 e 이하의 임의의 수 s를 여러 개가 주어질 때, 각 s에 대해서 s <= x <= e 인 x 중에서 가장 많이 등장한 수를 찾아야 한다.
  • 가장 많이 등장한 수가 여러 개면 그 중 가장 작은 수를 답해야 한다.
  • 1 <= e <= 5,000,000
  • 1 <= s의 개수 <= min(e, 100,000)
• 각 s에 대한 답을 리턴하기

 

풀이

• 수학적으로 (?) 각 숫자가 몇 번 나오는지 계산할 수 있다면 금방 풀리지 않을까?
  • = 약수의 개수
• 약수의 개수 구하기
  • 제곱근을 제외하고는 1x9 와 9x1 이렇게 각각 2개씩 셀 수 있다.
  • 제곱근까지 2개씩 세고, 제곱근이 정수면 1개 제외하기

 

def solution(e, starts):
    numbers = [0 for i in range(e+1)]
    numbers[1] = 1
    # 약수 개수 찾기
    for num in range(2, e+1):
        for i in range(1, int(num**0.5)+1):
            if num % i == 0:
                numbers[num] += 2
        
        if num**0.5 == int(num**0.5) :
            numbers[num] -= 1

    # 가장 큰 수 정렬하기
    big_numbers = [i for i in range(e+1)]
    for i in reversed(range(1, e)):
        if numbers[i] < numbers[big_numbers[i+1]]:
            big_numbers[i] = big_numbers[i+1]

    # 정답 찾기
    return [ big_numbers[s] for s in starts]

 

 

References

• 프로그래머스 Lv3 억억단을 외우자