[Python][DP] 억억단을 외우자 - 프로그래머스 Lv.3

[문제]

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

억억단은 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에는 중복되는 원소가 존재하지 않습니다.

 

입출력 예

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이 정답입니다.

 

[깨달은 점]

• append로 answer 배열을 만들었더니, 마지막 테스트케이스 시간 초과.

    for s in starts : 
        answer.append(max_list[s])

•  아래와 같이 수정하니 통과....  여기서 starts의 길이는 최대 100,000이다. 길이가 긴 반복문으로 append는 삼가자 !!

    answer = [max_list[s] for s in starts]

 

[코드]

def solution(e, starts):
    answer = []

    counts = [0] * (e+1)

    for i in range(1, e+1):
        if i*i <= e :
            counts[i*i] += 1
        for j in range(i+1, e+1):
            if i * j > e : 
                break
            counts[i*j] += 2

    max_list = [0] * (e+1)
    max_value = counts[1]
    max_i = 1
    for i in range(e, 0, -1):
        if counts[i] >= max_value : 
            max_list[i] = i 
            max_value = counts[i]
            max_i = i

        else : 
            max_list[i] = max_i
            
    return [max_list[s] for s in starts]