[Programmers Lv2, Java] 12923. 숫자 블록

그렙시에는 0으로 된 도로에 숫자 블록을 설치하기로 하였습니다. 숫자 블록의 규칙은 다음과 같습니다.

블록의 번호가 n 일 때, 가장 처음 블록은 n * 2번째 위치에 설치합니다. 그다음은 n * 3, 그다음은 n * 4, ...로 진행합니다.만약 기존에 블록이 깔려있는 자리라면 그 블록을빼고 새로운 블록으로 집어넣습니다.

예를 들어 1번 블록은 2,3,4,5, ... 인 위치에 우선 설치합니다. 그다음 2번 블록은 4,6,8,10, ... 인 위치에 설치하고, 3번 블록은 6,9,12... 인 위치에 설치합니다.

이렇게 3번 블록까지 설치하고 나면 첫 10개의 블록은 0, 1, 1, 2, 1, 3, 1, 2, 3, 2이됩니다.

그렙시는 길이가 1,000,000,000인 도로에 1번 블록부터 시작하여 10,000,000번 블록까지 위의 규칙으로 모두 놓았습니다.

그렙시의 시장님은 특정 구간의 어떤 블록이 깔려 있는지 알고 싶습니다.

구간을 나타내는 두 수 begin, end 가 매개변수로 주어 질 때, 그 구간에 깔려 있는 블록의 숫자 배열(리스트)을 return하는 solution 함수를 완성해 주세요.

제한 사항

• begin, end 는 1 이상 1,000,000,000이하의 자연수 이고, begin는 항상 end보다 작습니다.
• end - begin 의 값은 항상 10,000을 넘지 않습니다.

---

 

이런 문제를 푸는 가장 쉬운 방법은 브루트포싱이라고 해야하나? 뭐 그런방법인데,

그렇게하면 시간복잡도가 지옥으로 가버릴테니 그렇게 풀수는 없다.

 

그래서 생각해낸 방법은

블록 n은 k*n에 설치되니까, 설치된 블록은 그 약수중에 가장 큰 수일것이다 라는 가정이였다.

그래서 테스트케이스에 대입해보니 4=2*2->2, 6=2*3->3, 8=2*4->4, 9=3*3->3, 10=2*5->5 로 일치했다.

 

자연수 N의 약수 목록을 구하는 방법은 i=1 ~ sqrt(N) 까지 모두 나눠본다음 나머지가 0인 수들이 N의 제곱근보다 작은 약수들이고, 그렇게 구한 약수들을 가지고 N을 나누면 N의 제곱근보다 큰 약수들을 모두 구할 수 있다.

 

int[] answer = new int[(int) (end-begin+1)];
    for(long i = 0 ; i <= end-begin ; i++) {
        // 블록의 타입
        long type = 0;
        // 현재 찾아야할 블록의 위치값
        long currentBlock = begin+i;
        
        // 자신이 아닌 가장 큰 약수 구하기
        for(long j = 1 ; j <= Math.sqrt(currentBlock) ; j++) {
            if(currentBlock % j == 0) {
                long target = currentBlock/j;
                // 구한 약수가 현재블록 위치값보다 작고, 주어진 최대값 1000만보다 작은지 검사
                if(target < currentBlock && target <= 10000000){
                    type = target;
                    break;
                }
            }
        }
        
        answer[(int) i] = (int) type;
    }

 

그렇게 위와 같은 코드를 작성했다.

 

이렇게 테스트케이스를 돌릴 경우 Prime Number들의 블록 타입이 모두 0으로 나오는데,

어떻게 일반식으로 할 수 있을까... 생각해보다가 귀찮아서

if(currentBlock > 1 && type == 0) type = 1;

를 추가했다.

 

현재블록위치가 1번이 아닌데, 가장 큰 약수를 구할 수 없으면,

약수가 1과 자기자신뿐이라는 뜻이므로, Manually하게 1로 설정해줬다.

 

최고의 속도를 내는 코드인지는 모르겠지만 아무튼 합격