[프로그래머스] 억억단을 외자 (Python)

Problem : 코딩테스트 연습 - 억억단을 외우자 | 프로그래머스 스쿨 (programmers.co.kr)

Status : Solved

Time : ??????

 

---

 

문제 설명

 

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

억억단은 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]

 

 

---

 

풀이

억억단 배열 크기에 비해 최댓값 e의 크기가 매우 작으므로, 사실상 전체 정수를 기준으로 생각하고 풀이하면 된다.

핵심은 억억단 배열에 나타나는 숫자 개수를 미리 구하는 것이라고 생각할 수 있다. 이전에도 비슷한 문제를 다룬 적이 있다(다른 코드 저지 사이트지만)

[CodeUp/3090] [백준/1300] K번째 수 (Python) :: 마젠티노 IT개발스토리 (tistory.com)

[CodeUp/3090] [백준/1300] K번째 수 (Python)

 

핵심은, 이러한 배열의 경우 숫자의 등장 횟수는 약수 개수와 동일하다는 점이다. 따라서 파이썬으로 본 문제를 풀이하려면

1. 최대한 적은 경우의 수를 고려하여 약수의 개수를 구하고

2. 약수의 개수 배열을 부분 최댓값 리스트로 반환한다

 

가 되겠다. 일일히 시작값에 따라 모든 약수의 개수를 구한다면 시간 초과가 뜨므로, 메모이제이션 기법을 사용하는 게 훨씬 유리하다.

 

풀이 코드

def solution(e, starts):
    divisor_list = [0]*(e+1)
    min_s = min(starts)
    for i in range(1, e + 1):
        if i * i <= e:
            divisor_list[i*i] += 1
        for j in range(i+1, e + 1):
            n = i * j
            if n > e:
                break
            divisor_list[n] += 2
            
    max_div_list = [0]*(e+1)
    max_div_list[-1] = e
    for i in range(e-1, min_s-1, -1) :
        if divisor_list[max_div_list[i+1]] <= divisor_list[i] :
            max_div_list[i] = i
        else :
            max_div_list[i] = max_div_list[i+1]
    answer = [ max_div_list[s] for s in starts ]
    
    return answer