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

문제 설명

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

억억단은 1억 x 1억 크기의 행렬입니다. 억억단을 외우던 영우는 친구 수연에게 퀴즈를 내달라고 부탁하였습니다.
수연은 평범하게 문제를 내봐야 영우가 너무 쉽게 맞히기 때문에 좀 어렵게 퀴즈를 내보려고 합니다. 적당한 수 e를 먼저 정하여 알려주고 e 이하의 임의의 수 s를 여러 개 얘기합니다. 영우는 각 s에 대해서 s보다 크거나 같고 e 보다 작거나 같은 수 중에서 억억단에서 가장 많이 등장한 수를 답해야 합니다. 만약 가장 많이 등장한 수가 여러 개라면 그 중 가장 작은 수를 답해야 합니다.
수연은 영우가 정답을 말하는지 확인하기 위해 당신에게 프로그램 제작을 의뢰하였습니다. e와 s의 목록 starts가 매개변수로 주어질 때 각 퀴즈의 답 목록을 return 하도록 solution 함수를 완성해주세요.

 

문제 풀이

 이 문제는 총 3가지를 떠올려야 해결할 수 있습니다.

1. 가장 많이 등장하는 횟수의 수를 어떻게 찾을까?

2. e의 범위가 5,000,000이 최대이기에 약수를 어떻게하면 효율적으로 찾을 수 있을까?

3. 특정 범위에 따라 가장 작은 많이 등장한 수를 어떻게 찾을까?

 

1번) 구구단을 곰곰히 생각해보면 특정 수들의 곱으로 이루어져 있고 각각의 등장 횟수는 약수의 개수와 동일합니다.

ex) 1번 등장: 1 / 2번 등장: 2, 3, 5, 7 / 3번 등장: 4 / 4번 등장: 6, 8    ->    2의 약수: 1, 2/ 4의 약수: 1, 2, 4 / 8의 약수: 1, 2, 4, 8

 

2번) 약수를 효율적으로 구하기 위해 시간복잡도를 최소한으로 줄일 수 있는 방법에 대해 고민해야하고 저는 아래 코드와 같은 방식을 선택했습니다.

private int[] getDivisor(int e) {
   int[] divisor = new int[e+1];
        
   for (int i=1; i<=e; i++) {
       for (int j=1; j<=e/i; j++) {
           divisor[i*j] += 1;
       }
   }
        
   return divisor;
}

 

3번) 3번의 경우를 고려하지 못하고 반복문을 통해 매번 범위를 체크해주면 테스트 9, 10번에서 시간초과를 볼 수 있습니다. 왜냐하면 아무리 약수를 효율적으로 구했다고 한들 starts: 100,000개이고 start가 전부 5,000,000라면 100,000 * 5,000,000을 반복하게 되기 때문입니다.

 

이것을 해결하기 위해선 약수의 개수를 구한 배열을 뒤에서 부터 체크해주면 됩니다. 

8 -> 1로 반복할 때를 표로 나타내면 아래와 같습니다.

8	최솟값: 8 / 약수: 4	4	최솟값: 6 / 약수: 4
7	최솟값: 8 / 약수: 4	3	최솟값: 6 / 약수: 4
6	최솟값: 6 / 약수: 4	2	최솟값: 6 / 약수: 4
5	최솟값: 6 / 약수: 4	1	최솟값: 6 / 약수: 4

 따라서 [1-8]의 범위에서는 6이 나올 수 있고 [7-8]의 범위에선 8이 나오게 됩니다. 이걸 적용해주면 아래 코드와 같습니다.

private int[][] getMaxNumStore(int e, int[] divisor) {
   int[][] store = new int[e+1][2];
        
   store[e][0] = divisor[e];
   store[e][1] = e;
   for (int i=e-1; i>=1; i--) {
       if (divisor[i] >= store[i+1][0]) {
           store[i][0] = divisor[i];
           store[i][1] = i;
       } else {
           store[i][0] = store[i+1][0];
           store[i][1] = store[i+1][1];
       }
    }
        
    return store;
}

 

풀이 코드

// 억억단 많이 등장한 횟수 -> 약수의 개수가 젤 큰 놈!

class Solution {
    private final int MAX_SIZE = 5000000;
    public int[] solution(int e, int[] starts) {
        int[] answer = new int[starts.length];
        
        int[] divisor = getDivisor(e);
        int[][] store = getMaxNumStore(e, divisor);
        
        for (int i=0; i<starts.length; i++) {
            answer[i] = store[starts[i]][1];
        }
        
        return answer;
    }
    
    private int[][] getMaxNumStore(int e, int[] divisor) {
        int[][] store = new int[e+1][2];
        
        store[e][0] = divisor[e];
        store[e][1] = e;
        for (int i=e-1; i>=1; i--) {
            if (divisor[i] >= store[i+1][0]) {
                store[i][0] = divisor[i];
                store[i][1] = i;
            } else {
                store[i][0] = store[i+1][0];
                store[i][1] = store[i+1][1];
            }
        }
        
        return store;
    }
    
    private int[] getDivisor(int e) {
        int[] divisor = new int[e+1];
        
        for (int i=1; i<=e; i++) {
            for (int j=1; j<=e/i; j++) {
                divisor[i*j] += 1;
            }
        }
        
        return divisor;
    }
}

 

<출처>

프로그래머스