[JAVA] 프로그래머스 LEVEL2 숫자 블록

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

프로그래머스

코딩테스트 연습 > 연습문제 > 숫자 블록

 

난이도: LEVEL2

알고리즘 유형: 구현

 

풀이 설명 

제한 사항
1 <= begin ≤  end ≤ 1,000,000,000 (10억)

end - begin ≤ 5,000

 

중요

블록에 기록할 수 있는 최대 숫자는 10,000,000 이다. 

해당 조건을 지키지 않으면 테스트케이스 13번과 효율성 테스트를 전부 틀리게 된다.

 

시간 복잡도를 고려하지 않고

그냥 1 ~ 최대(천만)까지 나눠지는 수를 구하려고 하면 시간 초과가 발생한다.

최악의 상황 5,000 * 10,000,000

 

그럼 어떻게 구해야 할까? 

public static int calculate(int input){
    int max = 1;
    for(int i = 2; i * i <= input; i++){
        if(input % i == 0){
            max = i;
            if(input / i <= 10000000)
            return input / i;
        }
    }
    return max;
}

 

2부터 숫자의 제곱근까지 for문을 돌면서

만약 이번 케이스에서 나눠지면 max를 현재 i로 갱신하고 

만약 input / i 가 천만보다 작으면 해당 몫은 가장 큰 약수이면서 천만보다 작다는 조건이 지켜지니 바로 return한다. 

만약 모든 케이스에서 1000만 보다 작은 케이스가 없다면 갱신해온 max를 반환한다. 

 

for문의 최악의 시간 복잡도는 최대 10억 루트이다.

10억 루트는 31,622.xxx 이다. 

 

그럼 5000 * 31,622 = 158,110,000 정도면 거의 모든 케이스가 1.5초 안에 돌아간다. 

 

정답 코드 

import java.util.*;
class Solution {
    static boolean [] check;
    public int[] solution(long begin, long end) {
        int st = (int) begin;
        int en = (int) end; 
        int [] answer = new int [en - st + 1];
        Arrays.fill(answer, 1);
        for(int i = st; i <= en; i++){ 
            answer[i - st] = calculate(i);
        }
        if(st == 1) answer[0] = 0;
        return answer;
    }    
    public static int calculate(int input){
        int max = 1;
        for(int i = 2; i * i <= input; i++){
            if(input % i == 0){
                max = i;
                if(input / i <= 10000000)
                return input / i;
            }
        }
        return max;
    }
}

 

연산이 간단해서 효율성 테스트 5번인 0.1초가 최대로 나왔다.