억억단을 외우자

2025-04-30

#JAVA#프로그래머스

2분

문제 링크

문제 요약

•
억억단은 i × j로 구성된 곱셈표 (1억 × 1억 크기)

•
어떤 수 n의 등장 횟수 = n의 약수 쌍 개수

•
정수 e와 여러 개의 starts[]가 주어짐

•
각 start s에 대해 [s, e] 범위에서 가장 많이 등장한 수를 구함

•
등장 횟수가 같으면 더 작은 수 선택

문제 풀이 시간 : 1시간

문제 풀이

이 문제는 이해를 하는데 좀 오래 걸렸던 문제인 것 같다.

예시와 같이 e가 8이라면,

아래와 같은 경우의 수가 나온다.

Arduino

1 : 1 - 1*1
2 : 2 - 1*2 2*1
3 : 2 - 1*3 3*1
4 : 3 - 1*4 2*2 4*1
5 : 2 - 1*5 5*1
6 : 4 - 1*6 2*3 3*2 6*1 
7 : 2 - 1*7 7*1 
8 : 4 - 1*8 2*4 4*2 8*1

이거를 좀 자세히 보다보면 다른 것이 생각나는데~~(나는 생각 못함)~~

바로 약수의 개수이다.

1은 1개(1)

2는 2개(1,2)

4는 3개(1,2,4)

8은 4개(1,2,4,8)

즉, 억억단에 나온 개수가 약수의 개수인 것이다.

생각보다 쉬운 문제였다.

약수의 개수 구하기

Java

for (int i = 1; i <= e; i++) {
    for (int j = i; j <= e; j += i) {
        count[j]++;
    }
}

이 코드는 1부터 e까지 모든 수의 약수 개수를 구하는 코드이다.

이 코드에서는 i 부터 시작하여 i 의 배수마다 count 값을 1씩 증가시킨다.

결과적으로 count[n]은 n의 약수 개수를 나타낸다.

최대 등장 수 구하기

Java

int[] maxValue = new int[e + 1];
int maxNum = e;
for (int i = e; i >= 1; i--) {
    if (count[i] >= count[maxNum]) {
        maxNum = i;
    }
    maxValue[i] = maxNum;
}

이 코드는 뒤에서부터 최대 등장 수를 갖는 값을 저장하는 코드이다.

i부터 e까지 범위에서 가장 많이 등장한 수를 maxValue[i]에 저장한다.

count[i]가 현재 최대값보다 크거나 같으면 maxNum을 i로 갱신한다.

Java

for (int i = 0; i < starts.length; i++) {
    answer[i] = maxValue[starts[i]];
}

이 코드를 통해 각 시작값에 대한 최대 등장 수를 정답 배열에 저장한다.

정답 코드

Java

import java.util.*;

class Solution {
    
    public int[] solution(int e, int[] starts) {
        int[] answer = new int[starts.length];
        
        int[] count = new int[e + 1];
        
        for (int i = 1; i <= e; i++) {
            for (int j = i; j <= e; j += i) {
                count[j]++;
            }
        }

        int[] maxValue = new int[e + 1];
        int maxNum = e;
        for (int i = e; i >= 1; i--) {
            if (count[i] >= count[maxNum]) {
                maxNum = i;
            }
            maxValue[i] = maxNum;
        }

        for (int i = 0; i < starts.length; i++) {
            answer[i] = maxValue[starts[i]];
        }
        
        return answer;
    }
}