[구현] 숫자 블록 (실패분석 - 시간 초과)

접근

숫자 블록

사실 문제의 접근법은 간단했습니다.
현재 블록을 만들어준 가장 큰 약수를 구하는 것입니다.

접근법은 간단하지만 정말 길고 긴 여정으로 풀게 되었습니다.
총 3가지의 풀이가 존재합니다.
각 풀이별 실패한 이유에 대해서 설명해보려고 합니다.

효율성 시간 초과 풀이

import java.util.*;

class Solution {
    public ArrayList<Long> solution(long begin, long end) {
        ArrayList<Long> answer = new ArrayList<>();
        // 숫자 0이 적힌 블록 -> 다른 숫자
        // 블록에 적힌 번호 n , 가장 첫 블록은 n*2번째 위치 , 그 다음은 n*3...
        
        for(long i=begin;i<=end;i++){
            answer.add(init(i));
        }
        return answer;
    }
    static long init(long target){
        long t = target/2;
      
        if(target-1==0) return 0;
        
        for(long i=t; i>=1;i--){
            if(target%i==0){
                if(i<=10_000_000)
                   return i;
            
            }
        }
        
        return 1;
    }
}

위 풀이는 13개의 테스트 케이스는 모두 정답이지만
효율성 테스트에서 시간 초과가 발생합니다.

접근방법은 블록을 만들 수 있는 가장 큰 약수를 찾는 것이었습니다.
근데 만약에 그 수가 문제에서 주어진 가장 블록의 수와 가까운 소수라면 결국 n억 번의 연산을 마치고 나서 1을 반환받을 수도 있다는 생각이 들었습니다.

구글링을 통해 소수를 찾아보았는데 소수는 무한하며 그래서 엄청 큰 숫자에도 소수가 존재했습니다.
그래서 위와 같이 반절로 나누어 찾는 방법은 너무 많은 연산을 발생시킨다는 것을 깨달았습니다.

13번 테스트 케이스 실패 및 효율성 실패

import java.util.*;

class Solution {
    public ArrayList<Long> solution(long begin, long end) {
        ArrayList<Long> answer = new ArrayList<>();
        // 숫자 0이 적힌 블록 -> 다른 숫자
        // 블록에 적힌 번호 n , 가장 첫 블록은 n*2번째 위치 , 그 다음은 n*3...
        
        for(long i=begin;i<=end;i++){
            answer.add(init(i));
        }
        return answer;
    }
    static long init(long target){
        long t = (long)Math.sqrt(target);
       
        if(target==1) return 0;
        
        for(long i=2; i<=Math.sqrt(target);i++){
            if(target%i==0){
                if(target/i<=10_000_000)
                    return target/i;
                else
                    continue;
            }
        }
        return 1;
      
    }
}

이 풀이는 그래서 반절을 나누것이 아니라 가장 큰 약수를 구하기 위해서
소수를 구하는 방향으로 접근법을 변경하게 되었습니다.
결국 가장 큰 약수는 소수로 나누 수이기 때문입니다.
그 약수가 10,000,000을 넘는 경우 다음 소수로 넘어가게 두었습니다.

하지만 이 풀이에서 제가 13번 테스트 케이스를 실패한 이유가 무엇일까요?
긴 고민 끝에 알게되었습니다.

마지막까지 나누어떨어졌지만 10,000,000을 넘긴 경우입니다.
이 경우 이 블록의 번호는 for문을 벗어날 때 마지막 약수가 이 수의 번호가 됩니다.

하지만 저는 그 조건문 없이 바로 1을 저장하도록 두었기 때문에 13번 테스트 케이스에서 문제가 발생했습니다.

성공한 풀이

import java.util.*;

class Solution {
    public ArrayList<Long> solution(long begin, long end) {
        ArrayList<Long> answer = new ArrayList<>();
        // 숫자 0이 적힌 블록 -> 다른 숫자
        // 블록에 적힌 번호 n , 가장 첫 블록은 n*2번째 위치 , 그 다음은 n*3...
        
        for(long i=begin;i<=end;i++){
            answer.add(init(i));
        }
        return answer;
    }
    
    
    static long init(long target){
        // 1인 경우 바로 0 반환
        if(target==1) return 0;
        
        // 마지막까지 1_000_000보다 큰 경우 가장 큰 약수를 저장하기 위한 변수 선언
        long remain = 0;
        // 에라토스테네스의 체를 응용하여 for문
        for(long i=2; i<=Math.sqrt(target);i++){
            if(target%i==0){
                remain = i;
                if(target/i<=10_000_000)
                    return target/i;
            }
        }
        
        // 마지막까지 10_000_000보다 큰 경우 앞서 진행한 for문의 가장 큰 약수가 정답이 된다.
        // 그 블록의 번호의 시초
        if(remain !=0) return remain;
        
        
        // 소수인 경우 1을 반환
        return 1;
      
    }
}

결국 위 풀이는 제가 간과한 연산의 횟수가 마지막까지 10,000,000을 넘긴 경우의 어떻게 처리할 것인지 두 가지를 모두 고려하여 풀이를 만들게 되었습니다.

시간초과 없이 효율성테스트와 13번 테스트 케이스를 통과하게 되었습니다!