99클럽 코테 스터디 3일차 TIL

[level 3] 억억단을 외우자 - 138475

문제 링크

성능 요약

메모리: 91.6 MB, 시간: 7822.86 ms

구분

코딩테스트 연습 > 연습문제

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2024년 04월 15일 23:22:04

문제 설명

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

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

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

 

 

풀이

def solution(e, starts):
    # dp 배열은 각 숫자의 약수의 개수를 저장합니다.
    dp = [0] * (e + 1)
    # dp_idx 배열은 해당 인덱스까지의 수 중 가장 많은 약수를 가진 수를 저장합니다.
    dp_idx = [0] * (e + 1)

    # 2부터 e까지 모든 수에 대해
    for i in range(2, e+1):
        # i의 배수에 대해 약수의 개수를 증가시킵니다.
        for j in range(1, min(e//i + 1, i)):
            dp[i*j] += 2
    # 1부터 e의 제곱근까지 모든 정수 i에 대해
    for i in range(1, int(e**(1/2)) + 1):
        # i의 제곱은 약수의 개수를 1 증가시킵니다. (i*i는 한 번만 카운트되기 때문)
        dp[i**2] += 1

    # 가장 많은 약수를 가진 수를 찾기 위한 카운터
    cnt = 0
    # e부터 1까지 역순으로 탐색하며 dp_idx를 갱신합니다.
    for i in range(e, 0, -1):
        # 현재 숫자의 약수 개수가 현재까지 발견된 최대 약수 개수보다 많거나 같다면
        if cnt <= dp[i]:
            cnt = dp[i]
            dp_idx[i] = i
        else:
            # 현재 숫자보다 더 많은 약수를 가진 수가 이미 발견되었다면, 해당 수를 dp_idx에 저장합니다.
            dp_idx[i] = dp_idx[i + 1]

    # 결과를 저장할 리스트
    answer = []
    # starts 배열의 각 원소에 대해
    for s in starts:
        # s보다 작거나 같으면서 가장 많은 약수를 가진 수를 찾아 결과에 추가합니다.
        answer.append(dp_idx[s])

    return answer

1. 약수 구하는 방법이 다양하게 존재하지만, 널리 알려진 완전 탐색이나 해당 수의 제곱근으로 접근을 하게 되면 시간 초과를 맞이하게 된다.
2. 통과하기 위해서 변형이 필요한데, 2부터 e까지 수에 대해서 수를 추가하는데, 1을 제외하고 2부터는 모든 약수가 2 이상이기 때문에 2씩 추가한다. 
3. 그리고 4 와 같이 2*2 인 경우, 약수가 중복되므로 1을 증가시킨다.
4. 그러면 dp에는 idx는 0~e, val은 각 idx의 약수의 개수가 되는 것이다.
5. 이 수를 dp_idx에 현재까지 발견한 약수들 중 가장 많은 약수의 개수를 가진 수를 e부터 역순으로 세어가며 dp_idx에 dp의 idx를 추가 한다. 이때 같은 약수의 개수를 발견하면 역순이기때문에 더 작은 수로 갱신되게 된다. (8 => 6)
6. 만약 새롭게 갱신되지 않는다면 마지막에 발견된 수가 계속해서 dp_idx에 갱신되게 된다.
7. answer에 starts 내의 수를 하나씩 뽑아서 dp_idx의 s 순서에 해당하는 수를 answer에 추가한다.
8. [0,6,6,6,6,6,6,8,8] 에서 idx = 1, 3, 7 에 해당하는 수를 answer에 추가한다.
9. 그래서 답이 6, 6, 8이 된다. 

이번 문제를 해결하면서 

• 접근 방법이 약수를 구한다는 것을 바로 캐치할 수 있었다.
• 그러나, 억*억 이기 때문에 이 수를 어떻게 줄일 것인가에 대해서는 제곱근의 접근 보다 더 수를 줄일 수 있는 방법이 필요했다. 이 부분에서 막히게 되었다.
• 지금 이 문제를 풀고 있을때, 서버에 따라 해결될수도, 안 될수도 있다는 글들이 있어 조금 까다로운 문제라고 생각했다.
• 그렇더라도 통과되는 코드는 존재하니, 어느 부분에서 시간초과가 걸릴 수 있는지에 대해서도 공부해볼 수 있는 시간이었다.