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

문제 설명

영우는 천하제일 암산대회를 앞두고 있습니다. 암산보다는 암기에 일가견이 있는 영우는 구구단을 확장하여 억억단을 만들고 외워버리기로 하였습니다.

억억단은 1억 x 1억 크기의 행렬입니다. 억억단을 외우던 영우는 친구 수연에게 퀴즈를 내달라고 부탁하였습니다.
수연은 평범하게 문제를 내봐야 영우가 너무 쉽게 맞히기 때문에 좀 어렵게 퀴즈를 내보려고 합니다. 적당한 수 e를 먼저 정하여 알려주고 e 이하의 임의의 수 s를 여러 개 얘기합니다. 영우는 각 s에 대해서 s보다 크거나 같고 e 보다 작거나 같은 수 중에서 억억단에서 가장 많이 등장한 수를 답해야 합니다. 만약 가장 많이 등장한 수가 여러 개라면 그 중 가장 작은 수를 답해야 합니다.
수연은 영우가 정답을 말하는지 확인하기 위해 당신에게 프로그램 제작을 의뢰하였습니다. e와 s의 목록 starts가 매개변수로 주어질 때 각 퀴즈의 답 목록을 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 1 ≤ e ≤ 5,000,000
• 1 ≤ starts의 길이 ≤ min {e,100,000}
• 1 ≤ starts의 원소 ≤ e
• starts에는 중복되는 원소가 존재하지 않습니다.

입출력 예

e	starts	result
8	[1,3,7]	[6,6,8]

입출력 예 설명

억억단에서 1 ~ 8이 등장하는 횟수는 다음과 같습니다.

1번 등장 : 1
2번 등장 : 2, 3, 5, 7
3번 등장 : 4
4번 등장 : 6, 8

[1, 8] 범위에서는 6과 8이 각각 4번씩 등장하여 가장 많은데 6이 더 작은 수이므로 6이 정답입니다.
[3, 8] 범위에서도 위와 같으므로 6이 정답입니다.
[7, 8] 범위에서는 7은 2번, 8은 4번 등장하므로 8이 정답입니다.

풀이

• 프로그래머스 알고리즘 코딩테스트 연습 문제들이 풀다보니까 뫄뫄가 되는 확률이나 소수냐? 아니면 약수냐? 같은 문제들이 많이 나오고, 이건 그냥 수학 문제 아니냐? 같은 생각을 하게 됨.
• 진짜 코딩 실력으로 테스트하는 거면, 억억단 만든 다음에 원하는 카운팅해서 결과를 뽑아내겠지만, 지금 이런 문제들은 그쪽보다는 수학으로 풀어야 속도도 더 잘나오고, 코드도 더 짧아지고 그렇지 않을까? 생각된다.
• 이거 딱 봐도... 뭔지 알 것 같지 않나? 수포자라 숫자로는 설명 못해도 그림으로는 설명할 수 있다.

• 근데 문제 제한사항을 보면 억억단이라길래 억x억인 줄 알았는데,
  • 1 ≤ e ≤ 5,000,000
  • e는 500만까지다. 즉, 억억단이 아니라 5백만x5백만단
• 그리고 starts 배열의 길이는 최소 10만.
  • 1 ≤ starts의 길이 ≤ min {e,100,000}
  • 10만개의 배열을 카운팅한다? 당근 시간 초과다.
• 그러면 방법은 뭐다? 일반항을 찾는 수 밖에 없다.
  • 1보다 작거나 같은 수 : 1x1
  • 2보다 작거나 같은 수 : 1x1,2x2
  • 3보다 작거나 같은 수 : 1x1,2x2,3x2
  • 4보다 작거나 같은 수 : 1x1,2x2,3x2,4x3
  • 5보다 작거나 같은 수 : 1x1,2x2,3x2,4x3,5x2
  • 6보다 작거나 같은 수 : 1x1,2x2,3x2,4x3,5x2,6x4
  • 7보다 작거나 같은 수 : 1x1,2x2,3x2,4x3,5x2,6x4,7x2
  • 8보다 작거나 같은 수 : 1x1,2x2,3x2,4x3,5x2,6x4,7x2,8x4
  • 9보다 작거나 같은 수 : 1x1,2x2,3x2,4x3,5x2,6x4,7x2,8x4,9x3
  • 10보다 작거나 같은 수 : 1x1,2x2,3x2,4x3,5x2,6x4,7x2,8x4,9x3,10x4
• 규칙을 모르겠어.... ㅠ.ㅠ
  • 1, 2, 2, 3, 2, 4, 2, 4, 3, 4, ....
• 약수의 갯수를 구하는 공식 같은 건 없나...?
  • 볼프람 알파... 도와줘요.

• 있다. 디리클레 생성 함수
  • https://kr.mathworks.com/help/signal/ref/diric.html
  • 하지만 쉽지 않다. ㅋㅋㅋ
  • 수포자는 웁니다. ㅠ.ㅠ

디리클레(Dirichlet) 함수 또는 주기적 sinc 함수 - MATLAB diric - MathWorks 한국

• 파이썬 코드도 있으나 디감마, 로그감마 모듈을 임포트해야 합니다.
  • https://bab2min.tistory.com/610

[Python] 디리클레 분포 추정하기

• 일반 생성 기능
  • 여기도  ψ기호와, (0) 같은 의미를 어떻게 코드로 옮겨야 할지 모르겠으니... 거의 포기 상태.
  • sum_(n=0)^∞a_nx^n = (ψ_x^(0)(1) + log(1 - x))/log(x)
• 넘파이나 사이파이를 쓰지 않고 할 수 있 방법은 없을까?
  • 잠깐? 프로그래머스에서 넘파이 쓰는 사람 봤는데? 흠...
    • 디리클레 확률 분포만 되네... 그냥 랜덤한 값이 나온다.
  • 암튼 공부가 되었다.
    • 시그마 시퀸스, 타우 시퀸스 등으로 불리고,
    • 수열 An = DivisorSum[n, 1&]
    • 즉, n의 약수의 개수를 나타내는 수열이라고 한다.

• 포기다.
  • 역시 나는 뭐다?
  • 무지성이다!

def divisor_sum(n):
    divisors = set()
    divisors.add(1)# 1은 모든 수의 약수이므로 미리 추가해둔다
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n // i)
    divisors.add(n)  # 자기 자신도 약수이므로 추가해준다
    return len(divisors)

def solution(e, starts):
    answer = []
    sequence_of_numbers_of_divisors = []
    m = min(starts)
    leng = e+1 - m
    for i in reversed(range(m, e+1)):
        sequence_of_numbers_of_divisors.append(divisor_sum(i))
    #print(sequence_of_numbers_of_divisors)
    for s in starts:
        temp, tmax = 0, 0
        for i in range(e-s+1):
            if tmax <= sequence_of_numbers_of_divisors[i]:
                temp = e-i
                tmax = sequence_of_numbers_of_divisors[i]
            #print(e-i,":",sequence_of_numbers_of_divisors[i],end=",  ")
        #print("")
        answer.append(temp)
    return answer
    
테스트 1
입력값 〉	8, [1, 3, 7]
기댓값 〉	[6, 6, 8]
실행 결과 〉	테스트를 통과하였습니다.

• 왠지 속도 안나올 것 같다.
• 역시...

정확성  테스트
테스트 1 〉	통과 (0.02ms, 10.1MB)
테스트 2 〉	통과 (0.03ms, 10.4MB)
테스트 3 〉	통과 (0.18ms, 10.3MB)
테스트 4 〉	통과 (1.71ms, 10.1MB)
테스트 5 〉	통과 (6.53ms, 10.4MB)
테스트 6 〉	통과 (186.16ms, 10.2MB)
테스트 7 〉	통과 (292.61ms, 10.3MB)
테스트 8 〉	통과 (9071.45ms, 11.1MB)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)

• 대충 이렇게 하면 될까 싶었지만 (속도만 알고 싶었음) 마찬가지로 시간 초과

def divisor_sum(n):
    divisors = set()
    divisors.add(1)# 1은 모든 수의 약수이므로 미리 추가해둔다
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n // i)
    divisors.add(n)  # 자기 자신도 약수이므로 추가해준다
    return len(divisors)

def solution(e, starts):
    answer = []
    sequence_of_numbers_of_divisors = []
    m = min(starts)
    leng = e+1 - m
    for i in reversed(range(m, e+1)):
        sequence_of_numbers_of_divisors.append(divisor_sum(i))
    #print(sequence_of_numbers_of_divisors)
    copied_starts = starts.copy()
    copied_starts.sort(reverse=True)
    #print(copied_starts) 큰 수부터
    x, temp, tmax = 0, 0, 0
    for i in range(e-m+1):
        if tmax <= sequence_of_numbers_of_divisors[i]:
            temp = e-i
            tmax = sequence_of_numbers_of_divisors[i]
        if copied_starts[x] == e-i:
            answer.append(temp)
            x += 1
    #print(copied_starts, starts)
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.02ms, 10.4MB)
테스트 2 〉	실패 (0.05ms, 10.2MB)
테스트 3 〉	실패 (0.17ms, 10.2MB)
테스트 4 〉	실패 (0.88ms, 10.1MB)
테스트 5 〉	실패 (3.59ms, 10.2MB)
테스트 6 〉	실패 (21.55ms, 10.2MB)
테스트 7 〉	실패 (73.95ms, 10.5MB)
테스트 8 〉	실패 (435.30ms, 10.9MB)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)

• 모든 약수의 갯수를 구하는 방식으로 하면 안되나 봄...
  • 여기까지 11시 50분.
  • 약수의 갯수 구하는 문제 그만 좀 나왔으면 좋겠네...
• 결국 검색의, 검색의, 검색의...
  • 약수의 갯수를 통으로 빠르게 구하는 방법.

def solution(e, starts):
    divisor=[0 for i in range(e+1)]
    for i in range(2,e+1):
        for j in range(1,min(e//i+1,i)):
            divisor[i*j]+=2
    for i in range(1,int(e**(1/2))+1):
        divisor[i**2]+=1

• 위 코드로 약수의 갯수를 빠르게 찾아놓고,
• starts를 역으로 정렬해서 큰 값부터 작은 값으로 내려오면서 찾는다.
• 다 끝나고 위치 맞추기 해야함. 중복 되는 원소가 없다니까 max로 값을 찾고, 그 값의 index를 찾아서, 위치 맞춰주면 될 듯? 어우야... 더 간단한 방법없나? 배열 정렬할 때 위치를 기록해주거나...
  • 는 넘파이에 아그소트 기능을 사용하자!
• 실패하긴 하는데 시간 초과로 터지지는 않는다.
  • 큰 수 부터 찾지 않고 그냥 해볼까?

import numpy as np

def solution(e, starts):
    answer = []
    divisors = [0 for i in range(e+1)]
    
    for i in range(2, e+1): # 개빠름
        for j in range(1,min(e//i+1,i)):
            divisors[i*j] += 2
            
    for i in range(1, int(e**0.5)+1):
        divisors[i**2] += 1
    
    reversed_starts = np.sort(starts)[::-1]
    reversed_index = np.argsort(starts)[::-1]
    
    x, temp, tmax, m = 0, 0, 0, min(reversed_starts)
    
    for i in reversed(range(m,e+1)):
        if tmax <= divisors[i]:
            temp = i
            tmax = divisors[i]
            
        if reversed_starts[x] == i:
            answer.append(temp)
            x += 1
    
    answer_sorted = [answer[i] for i in reversed_index]
    return answer_sorted
    
정확성  테스트
테스트 1 〉	통과 (0.04ms, 28.2MB)
테스트 2 〉	실패 (0.06ms, 28.3MB)
테스트 3 〉	실패 (0.14ms, 28.3MB)
테스트 4 〉	실패 (0.46ms, 28.5MB)
테스트 5 〉	실패 (1.01ms, 28.2MB)
테스트 6 〉	실패 (4.70ms, 28.4MB)
테스트 7 〉	실패 (12.22ms, 28.6MB)
테스트 8 〉	실패 (53.17ms, 28.8MB)
테스트 9 〉	실패 (1724.01ms, 40.1MB)
테스트 10 〉	실패 (9404.31ms, 74.7MB)

• 그냥 맨 처음 방법으로 해보기
  • 안됌. 시간 초과남.

import numpy as np

def solution(e, starts):
    answer = []
    divisors = [0 for i in range(e+1)]
    
    for i in range(2, e+1): # 개빠름
        for j in range(1,min(e//i+1,i)):
            divisors[i*j] += 2
            
    for i in range(1, int(e**0.5)+1):
        divisors[i**2] += 1
    
    for s in starts:
        temp, tmax = 0, 0
        for i in reversed(range(s,e+1)):
            if tmax <= divisors[i]:
                temp = i
                tmax = divisors[i]
        answer.append(temp)
    
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 28.5MB)
테스트 2 〉	통과 (0.02ms, 28.1MB)
테스트 3 〉	통과 (0.09ms, 28.2MB)
테스트 4 〉	통과 (1.40ms, 28.2MB)
테스트 5 〉	통과 (4.22ms, 28.2MB)
테스트 6 〉	통과 (83.54ms, 28.4MB)
테스트 7 〉	통과 (269.83ms, 28.4MB)
테스트 8 〉	통과 (7996.83ms, 29.3MB)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)

• 막힘 ㅋㅋ
• 힌트 힌트 힌트 ㅠ.ㅠ
• 힌트 최대한 안보려고 했는데 도무지 갈피를 못 잡겠고, 잠은 자고 싶고...
• 그러다가 DP로 풀어야 한다는 걸 보고... 아... 했따.

def solution(e, starts):
    answer = []
    divisors = [0 for i in range(e+1)]
    answers = [0 for i in range(e+1)]
    temp = 0
    
    for i in range(2, e+1):
        for j in range(1,min(e//i+1,i)):
            divisors[i*j] += 2
    for i in range(1, int(e**0.5)+1):
        divisors[i**2] += 1
    
    for i in reversed(range(e+1)):
        if divisors[i] >= temp:
            temp = divisors[i]
            answers[i] = i
        else:
            divisors[i] = temp
            answers[i] = answers[i+1]
    
    for i in starts:
        answer.append(answers[i])
        
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.03ms, 10.1MB)
테스트 3 〉	통과 (0.12ms, 10.2MB)
테스트 4 〉	통과 (0.37ms, 10.2MB)
테스트 5 〉	통과 (1.36ms, 10.2MB)
테스트 6 〉	통과 (6.35ms, 10.3MB)
테스트 7 〉	통과 (16.73ms, 10.3MB)
테스트 8 〉	통과 (47.26ms, 11.1MB)
테스트 9 〉	통과 (1497.45ms, 28.5MB)
테스트 10 〉	통과 (8128.52ms, 91.6MB)

• 풀고 나니 레벨 3 문제였네?
• 레벨2 카카오 블라인드 채용 문제 지겨워서 난이도 체크 바꾸다가 풀린 듯... 크흡...
• 고수들의 풀이를 보도록 하자.
  • 이건 통과된 코드인데 지금은 시간초과 난다.

def solution(e, starts):
    arr = [1]*(e+1)
    ans = [0]*(e+1)
    i = 2
    for i in range(2,e+1):
        for j in range(i*2,e+1,i):
            arr[j] += 1
    ans[e] = e
    for i in reversed(range(0,e)):
        if arr[i] >= arr[ans[i+1]]:
            ans[i] = i
        else:
            ans[i] = ans[i+1]
    return [ans[i] for i in starts]
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.3MB)
테스트 3 〉	통과 (0.10ms, 10.1MB)
테스트 4 〉	통과 (0.68ms, 10.2MB)
테스트 5 〉	통과 (1.52ms, 10.1MB)
테스트 6 〉	통과 (7.90ms, 10.1MB)
테스트 7 〉	통과 (16.89ms, 10.4MB)
테스트 8 〉	통과 (103.20ms, 11MB)
테스트 9 〉	통과 (2114.45ms, 28.4MB)
테스트 10 〉	실패 (시간 초과)

• 메모이제이션 방식, 엄청 빠름. 왤케 빠르지?
  • e_sqrt 한번만 계산? (근데 내 코드에선 이걸 따로 빼면 더 느려짐)
  • 메모이제이션으로 약수 갯수 구함.
  • 약수갯수가 많은 숫자로 갱신하는 코드도 이쁘다. 근데 속도랑 상관없어 보이는데...
  • 마지막에 answer 리스트에 append( )하지 않고 start에 값 덮어씌움.
  • 거기도 memo[start] 값을 넣어버리네... 한 줄 한 줄이 예술이다. 근데 속도랑 관련있나?

def solution(e, starts):
    memo = [0] * (e+1)
    e_sqrt = int(pow(e, 0.5))
    for n in range(1, e_sqrt+1):
        memo[n*n] += 1
        for i in range(n*(n+1), e+1, n):
            memo[i] += 2

    max_val = max_num = 0
    for i in range(e, 0, -1):
        if memo[i] >= max_val:
            max_val, max_num = memo[i], i
        memo[i] = max_num

    for i, start in enumerate(starts):
        starts[i] = memo[start]

    return starts
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.02ms, 10.2MB)
테스트 3 〉	통과 (0.06ms, 10.1MB)
테스트 4 〉	통과 (0.26ms, 10.1MB)
테스트 5 〉	통과 (0.56ms, 10.1MB)
테스트 6 〉	통과 (2.54ms, 10.3MB)
테스트 7 〉	통과 (7.40ms, 10.2MB)
테스트 8 〉	통과 (39.25ms, 10.6MB)
테스트 9 〉	통과 (947.92ms, 19.9MB)
테스트 10 〉	통과 (5627.77ms, 52.7MB)

• 약수를 구하는 부분이 더 빠른 거였구나?
  • 약수 구하는 부분만 교체하니까 더 빨라짐

def solution(e, starts):
    answer = []
    divisors = [0 for i in range(e+1)]
    answers = [0 for i in range(e+1)]
    temp = 0

    '''
    for i in range(2, e+1):
        for j in range(1,min(e//i+1,i)):
            divisors[i*j] += 2
    for i in range(1, int(e**0.5)+1):
        divisors[i**2] += 1
    '''
    e_sqrt = int(pow(e, 0.5))
    for n in range(1, e_sqrt+1):
        divisors[n*n] += 1
        for i in range(n*(n+1), e+1, n):
            divisors[i] += 2
            
    for i in reversed(range(e+1)):
        if divisors[i] >= temp:
            temp = divisors[i]
            answers[i] = i
        else:
            divisors[i] = temp
            answers[i] = answers[i+1]

    for i in starts:
        answer.append(answers[i])

    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.03ms, 10.2MB)
테스트 3 〉	통과 (0.09ms, 10.1MB)
테스트 4 〉	통과 (0.20ms, 10.2MB)
테스트 5 〉	통과 (0.62ms, 10.1MB)
테스트 6 〉	통과 (4.71ms, 10.2MB)
테스트 7 〉	통과 (6.59ms, 10.5MB)
테스트 8 〉	통과 (30.91ms, 11.2MB)
테스트 9 〉	통과 (805.40ms, 28.4MB)
테스트 10 〉	통과 (5287.40ms, 91.4MB)

• 그리고 e_sqrt라는 변수를 하나 만들어서 for문에 사용하는 방식은 더 느림.
  • 그냥 int(e**0.5)로 수정시 조금 더 빨라짐.

def solution(e, starts):
    answer = []
    divisors = [0 for i in range(e+1)]
    answers = [0 for i in range(e+1)]
    temp = 0

    for n in range(1, int(e**0.5)+1):
        divisors[n*n] += 1
        for i in range(n*(n+1), e+1, n):
            divisors[i] += 2
            
    for i in reversed(range(e+1)):
        if divisors[i] >= temp:
            temp = divisors[i]
            answers[i] = i
        else:
            divisors[i] = temp
            answers[i] = answers[i+1]

    for i in starts:
        answer.append(answers[i])

    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.03ms, 10.2MB)
테스트 3 〉	통과 (0.05ms, 10.1MB)
테스트 4 〉	통과 (0.20ms, 10.3MB)
테스트 5 〉	통과 (0.42ms, 10.3MB)
테스트 6 〉	통과 (2.47ms, 10.3MB)
테스트 7 〉	통과 (4.68ms, 10.4MB)
테스트 8 〉	통과 (26.23ms, 11.2MB)
테스트 9 〉	통과 (713.76ms, 28.5MB)
테스트 10 〉	통과 (4508.23ms, 91.5MB)

• 좋은 거 많이 알았따...