프로그래머스 Java Lv2 숫자 블록

 

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

 

해당 문제는 숫자 블록이 배치되는 규칙성을 찾으면 쉽게 풀 수 있는 문제이다.

 

숫자 n이 적힌 블록들이 n*2, n*3, n*4, ... 위치에 배치된다.          (배치 위치)

또한 숫자 n은 1 부터 시작하여 10,000,000 (천만)까지 이며,        (증가 순서 ,크기 제한)

뒤에 배치되는 블록이 먼저 배치된 블록 대신 배치되게 된다.        (갱신)

 

이러한 규칙으로 블록을 배치하게 되면 어떠한 위치 a에 배치되는 숫자는

"어떠한 위치 a 의 약수 중 자신을 제외한 가장 큰 수" 이다.

 

예를 들어 10번 째 위치를 생각해보자.

10번 째 위치에 배치될 수 있는 숫자 블록은 1, 2, 5 이다.

 

1을 10번 째 배치 1*10 위치  /  2를 5번 째 배치 2*5 위치  /  5를 2번 째 배치 5*2 위치

또한 n은 1부터 시작되어 이후 배치되는 블록으로 갱신되므로 10번째 위치에는 최종적으로 5가 배치된다.

 

이 때 위치는 최대 1,000,000,000 (10억) 이지만 숫자는 최대 10,000,000 (천만) 이므로 

다시 정리하면 "어떠한 위치 a의 약수 중 자신을 제외하고, 10,000,000 이하인 가장 큰 수 이다."

 

 

이것을 코드로 표현하면 다음과 같다.

class Solution {
    public int[] solution(long begin, long end) {

        int[] answer = new int[(int) (end - begin) + 1];

        for (int i = 0; i < answer.length; i++) {
            long num = begin + i;

            //약수 구하기
            int max_divisor = 1;
            for (long div = 2; div <= Math.sqrt(num); div++) {
                if (num % div == 0) {
                    //최대 10억의 제곱근이므로 약 3만으로, 천만 이하인지 검사X
                    int divisor1 = (int) div; 
                    //최대 10억 / 2,  5억이므로 천만이하인지 검사 필요함
                    int divisor2 = (int) (num / div);
                    
                    //가장 큰 약수 찾기
                    max_divisor = Math.max(max_divisor, divisor1);
                    if ( divisor2 <= 10000000)
                        max_divisor = Math.max(max_divisor, divisor2);
                }
            }
            answer[i] = max_divisor;
        }
        if (begin == 1)
            answer[0] = 0;
        return answer;
    }
}

<코드 1 / 가독성 좋음, 성능 낮음>

 

class Solution {
    public int[] solution(long begin, long end) {
        int[] answer = new int[(int) (end - begin) + 1];

        for (int i = 0; i < answer.length ; i++) {
            long num = begin + i;

            for (long div = 2; div <= Math.sqrt(num); div++) {
                if (num % div == 0) {
                    if (num / div > 10000000){
                        answer[i] = (int) div;
                        continue;
                    } else{
                        answer[i] = (int) (num / div);
                    }
                    break;
                }
            }
            if (answer[i] == 0) //소수인 경우
                answer[i] = 1; //약수가 1과 자기자신 밖에 없다.
        }
        if (begin == 1)
            answer[0] = 0;
        return answer;
    }
}

<코드 2 / 가독성 낮음, 성능 좋음>

 

 

코드 1의 경우 가독성 측면에서는 좋으나

모든 약수를 찾고 그 중에서 가장 큰 약수를 계산하기 때문에 성능은 비교적 떨어진다.

 

코드 2의 경우 가독성은 안좋으나

가장 큰 약수가 나오면 반복문이 정지하여 성능이 좋다.

 

약수를 계산하는 부분을 집중해서 보자.

어떠한 수를 나누는 수(div)가 약수라면 그 수로 나누었을 때 몫(num/div) 또한 약수이다.

즉 가장 큰 약수는 가장 처음 나온 (num / div) 값 이다.

 

하지만 가장 처음 나온 (num / div) 값이 10,000,000 을 넘는다면 그 수는 불가능하다.

그러므로 우선 div 값을 저장하고 다른 약수들이 있는지 계산한다.

만약 없다면 저장된 div 값이 가장 큰 약수이다.