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

https://school.programmers.co.kr/learn/courses/30/lessons/138475

프로그래머스

코딩테스트 연습 > 연습문제 > 억억단을 외우자

 

난이도: LEVEL3

알고리즘 유형: 구현(수학)

풀이 설명

예시로 주어진

1 ~ 8 숫자 범위를 분석해 보자.

	1	2	3	4	5	6	7	8
1	1	2	3	4	5	6	7	8
2	2	4	6	8
3	3	6
4	4
5	5
6	6
7	7
8	8

 

1: 1번 등장 

2: 2번 등장 

3: 2번 등장 

4: 3번 등장 

5: 2번 등장

6: 4번 등장

7: 2번 등장

8: 4번 등장 

 

등장 횟수를 보면 특정 숫자의 억억단에서 등장 횟수는 해당 숫자의 약수 개수이다. 

 

제한사항으로 주어진 e의 최대 크기는 5,000,000 

 

그럼 먼저 1부터 e까지 각 숫자들의 약수의 개수를 구한다. 

→ 억억단에서 등장 횟수 

 

미리 구해진 등장 횟수를 바탕으로 

특정 범위 starts[i] ~ e 까지 숫자 중에 가장 등장 횟수가 많고 등장 횟수가 같다면 작은 숫자를 구한다. 

시간 초과 코드 (80점)

import java.util.*;
class Solution {
    public int[] solution(int e, int[] starts) {
        int [] memo = new int [e + 1];
        Arrays.fill(memo, 1);
        for(int i = 2; i <= e; i++){
            for(int j = 1; j * i <= e; j++){
                memo[i *j]++;
            }
        }
        int [] answer = new int [starts.length];
        
        for(int i = 0; i < starts.length; i++){
            int begin = starts[i];
            int s = begin;
            int max = 1;
            for(int j = begin; j <= e; j++){
                if(memo[j] > max){
                    max = memo[j];
                    s = j;
                }
            }
            answer[i] = s;
        }       
        return answer;
    }
}

 

해당 코드는 2가지 케이스에서 시간 초과를 받는다. 

 

starts의 길이가 최대  5,000,000 인데 

그럼 최악의 경우 O(n^2)의 시간 복잡도인데 

그럼  5,000,000 * 5,000,000 시간이 걸린다. 

 

개선 방법 

탐색 범위의 끝부분은 언제나 e이다. 

starts[i]가 큰 순서대로 정렬을 하고 

해당 숫자부터 탐색을 하고 탐색 범위를 starts[i] 에서 갱신된 e까지 탐색한다.

그 이후의 숫자는 이미 탐색하였고 크기가 같다면 작은 숫자를 반영하니까 가능한 일이다.

 

개선 예시

 

e가 8 starts[1,3,7]이라면 

 

1. 7 ~ 8 범위 탐색  탐색 끝 범위: 7 변경 

2. 3 ~ 7 범위 탐색  탐색 끝 범위: 3 변경 

3. 1 ~ 3 범위 탐색 

정답 코드 

import java.util.*;
class Solution {
    public int[] solution(int e, int[] starts) {
        // 약수 구하기 
        int [] memo = new int [e + 1];
        Arrays.fill(memo, 1);
        for(int i = 2; i <= e; i++){
            for(int j = 1; j * i <= e; j++){
                memo[i *j]++;
            }
        }
        int size = starts.length; // 100000 최대 
        ArrayList<int[]> list = new ArrayList<>();
        for(int i = 0; i < size; i++){
            list.add(new int [] {i, starts[i]});
        }
        // starts 숫자가 큰 순서대로 정렬
        list.sort((o1,o2)->{
           return o2[1] - o1[1];
        });
        
        int end = e; // 탐색 범위 
        int max = 1;
        int v   = e;
        int [] answer = new int [size];
        for(int i = 0; i < size; i++){
            int [] temp = list.get(i);
            int start = temp[1];
            for(int j = end; j >= start; j--){
                if(memo[j] >= max){ // 크거나 같으면 갱신 
                    max = memo[j];
                    v = j;
                }    
            }
            end = start; // 범위 줄이기 
            answer[temp[0]] = v; // 정답 기록 
        }
        return answer;
    }
}