[프로그래머스,자바] Level2: 숫자블록

 

문제분석:

 

블록을 다음과 같은 규칙으로 칠한다.  N*2 , N*3, ...일경우 블록을 칠한다.

 

이미 블록이 칠해져있다면 덮어서 칠한다.

 

여기서 칠해야하는 블록의 갯수가 무려 10억개,  각기다른 블록의색깔은 천만개다.

   

잘못 구현하면 바로 효율성에러가 뜨기좋은 거대한 숫자다.

 

 

문제의 요구사항은  begin~ end 사이에있는 블록의 리스트다.

 

그러면 필시  begin~end 부터 돌릴 반복문 1개가 존재해야한다.

 

그렇다면 begin~ end의 블록의 색깔은 어떻게 구할까?

 

이 블록의 색깔은 제일 작은 소수로 나눈 몫이 블록의 색깔이된다. 

 

제일 작은 소수를 구하는법은 에라토네스의 체를 사용한다.

 

여기서 주의해야할점은 리턴하는 몫의 값이  천만을 넘어가선 안된다.

블록이 천만개만 존재하기때문에 그 이상의 블록의색깔은 존재하지않기때문이다.

문제풀이

import java.util.*;
class Solution {
    public List<Integer> solution(long begin, long end) {
        int[] answer ={};
        
        List<Integer> board = new ArrayList<>();
        
        int length=(int)(end-begin+1);
        answer= new int[length];
        
        for(long i=begin;i<=end;i++){           
            if(i==1){
                   board.add(0);
                   continue;
               }
            else{              
               board.add((int)block(i));
            }
            //에라토네스의 체 응용
        }
      
        return board;
    }
    
    public long block(long n){
        for(long i=2;i<=Math.sqrt(n);i++){   
            if(n%i==0){
                if(n/i>10000000){
                    continue;
                }
                return n/i;
            }
        }     
        return 1;
    }
}