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

문제

코딩테스트 연습 - 억억단을 외우자

알고리즘 문제 연습 카카오톡 친구해요! 프로그래머스 교육 카카오 채널을 만들었어요. 여기를 눌러, 친구 추가를 해주세요. 신규 교육 과정 소식은 물론 다양한 이벤트 소식을 가장 먼저 알려드립니다.

school.programmers.co.kr

문제 정리

요약

• 구구단을 확장하여 억억단을 만들었습니다.
• e가 주어지고 e 보다 작은 수 s 여러 개 주어집니다.
• 각 s에 대하여 s 보다 크거 같고 e 보다 작거나 같은 수 중에서 가장 많이 등장하는 수를 찾아야 합니다.

입력 조건

• e : 1 ~ 5,000,000
• s의 목록 starts
  • starts 길이 : 1 ~ min(e, 105)
  • starts에는 중복되는 원소가 존재하지 않습니다.

출력

• 각 s에 대한 답 목록
• 만약 가장 많이 등장하는 수가 여러 개라면 그 중 가장 작은 수가 정답입니다.

---

문제 풀이

구구단에 특정 숫자가 등장하는 횟수는 해당 숫자를 만드는 (a x b) 쌍의 개수를 의미합니다. 이는 곧 특정 숫자의 약수 개수와 같습니다.

따라서 문제는 다음과 같이 정리할 수 있습니다.

각 s에 대하여 [s, e] 구간에서 약수의 개수가 가장 많은 수를 찾기. (동일하면 더 작은 수 선택)

---

브루트포스 접근

구간 내에서 약수의 개수가 가장 많은 수를 찾는 방법으로 가장 직관적인 방법은 구간 전부 탐색하는 것입니다.

for (int s: starts) {
    int maxDiv = 0; // 최대 약수의 개수
    int result = 0; // 약수 주인
    for (int i = s; i <= e; i++) {
        // div[i] : 숫자 i의 약수의 개수
        if (div[i] > maxDiv) {
            maxDiv = div[i];
            result = i;
        }
    }
    answer.add(result);
}

하지만 해당 방식은 최악의 경우

• starts 길이: 10⁵
• 각 탐색 최대 범위 : 5 x 10⁶

이므로 전체 시간복잡도는 O(1011) 시간초과 나게 됩니다.

---

핵심 아이디어

여기서 주목할 특징은 모든 탐색의 끝점이 e로 고정되어 있다는 점입니다.

즉, 다음과 같은 형태의 문제를 반복해서 풀고 있습니다.

• [s1, e]
• [s2, e]
• …

이 구조를 활용하면, 뒤에서부터 값을 계산하는 방식으로 최적화할 수 있습니다. i ~ e 범위내에서 가장 많은 약수를 가지는 수(k)를 알고 있다면 i - 1 ~ e 범위내에서 가장 많은 약수는 k와 i의 약수 개수 비교를 통하여 바로 구할 수 있습니다. 이를 이용하여 DP와 점화식을 다음과 같이 정의할 수 있습니다.

DP 정의

DP[i]를 구간 [i, e]에서 약수의 개수가 가장 많은 수로 정의합니다.

점화식

• div[i] >= div[DP[i + 1]] -> DP[i] = i
• div[i] < div[DP[i + 1]] -> DP[i] = DP[i + 1]

즉, 현재 값(i)이 더 많은 약수를 가지면 갱신하고, 아니면 기존 최적값을 그대로 가져와서 계산할 수 있습니다.

---

풀이 코드

class Solution {
    public int[] solution(int e, int[] starts) {
        int[] answer = new int[starts.length];

        // 각 수의 약수의 개수
        int[] divisors = new int[e + 1];

        // 1 ~ e 까지 각 수의 약수 개수 구하기.
        for (int i = 1; i <= e; i++) {
            for (int j = i; j <= e; j += i) {
                divisors[j] += 1;
            }
        }

        // dp[i]: i ~ e 사이 수 중에서 약수가 가장 많은수
        int[] dp = new int[e + 1];

        // DP 구축
        dp[e] = e;

        for (int i = e - 1; i > 0; i--) {
            if (divisors[i] >= divisors[dp[i + 1]]) {
                dp[i] = i;
            } else {
                dp[i] = dp[i + 1];
            }
        }

        // 해 구하기
        for (int i = 0; i < answer.length; i++) {
            answer[i] = dp[starts[i]];
        }

        return answer;
    }
}