[프로그래머스] 숫자 블록 - Java

문제 설명

 

프로그래머스

 

접근 방법

길이가 10억인 도로가 있을 때, 도로 상 위치 1부터 위치 10억까지 각각의 위치에 1번 블록 ~ 1천만 블록을 문제에서 주어진 규칙대로 배치해야한다.

 

이때 도로 상 각각의 위치에 올 수 있는 숫자 블록에는 일종의 규칙이 있다. 위치를 나타내는 해당 수(1 ~ 10억)가 "소수"일 경우에는 반드시 1이라는 점이다. 소수는 1과 1이 아닌 자기 자신으로만 나눠지는 수로서 1 외에는 n * 2, n * 3, n * 4, ... 등의 값의 형태를 띄는 숫자 블록이 나올 수가 없다.

 

이를 위해 다음과 같이 소수를 판별하는 간단한 로직을 작성해보았다.

 

    public boolean isPrime(int n) {
        if (n < 2) {
            return false;
        }

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }

        return true;
    }

 

만일 소수가 아니라면 어떤 규칙이 있을까? 바로 해당 수에 대한 약수 중 자기 자신의 수를 제외한 가장 큰 수가 나온다. 예를 들어 10이라는 위치에는 5가 나오는데, 이는 10을 제외하면 10의 약수 중 가장 큰 수이다.

 

숫자 블록은 n * 2, n * 3, n * 4, ... 규칙에 따른 위치에 놓이게 되는데, 10이라는 위치에는 최초 1(숫자 블록) * 10에 의해 1이 배치되고, 이후 2 * 5에 의해 2가 배치되고, 5 * 2에 의해 5가 배치되면서 이후로 배치되는 숫자 블록은 전무하다.

 

소수를 판별하는 로직과 더불어 최대 약수를 구하는 로직을 다음과 같이 작성하였다. 참고로 숫자 블록은 최대 1천만이므로 그 이상 넘지 못하도록 별도 설정했다. (1천만이 넘는 위치의 값이 소수가 아니면서 1천만 이하의 약수가 없는 경우에는 해당 위치에 숫자 블록 1이 나올 것이다.)

 

    private int getMaxDivisor(int number) {
        if (number == 1) {
            return 0;
        }

        int result = 1;

        for (int i = 2; i <= Math.sqrt(number); i++) {
            if (number % i == 0 && number / i <= 10000000) {
                result = number / i;
                break;
            }
        }

        return result;
    }

 

소수 판별과 최대 약수를 구하는 로직 상 공통적으로 for문의 탐색 범위를 해당 수의 제곱근까지로 두었는데, 특정 수에서 존재할 수 있는 최대 약수값(자기 자신 제외)은 해당 수의 제곱근 이하이기 때문이다.

 

최종적으로 이 두 개의 로직을 이용하여 인자로 주어지는 begin과 end 사이에 도로 위치 값들에 대해 숫자 블록을 배치하면 된다.

 

전체 소스 코드

class Solution {
    
    public int[] solution(long begin, long end) {
        int[] result = new int[(int) (end - begin + 1)];
        int index = 0;
        for (int i = (int) begin; i <= end; i++, index++) {
            if (isPrime(i)) {
                result[index] = 1;
            } else {
                result[index] = getMaxDivisor(i);
            }
        }

        return result;
    }

    public boolean isPrime(int n) {
        if (n < 2) {
            return false;
        }

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }

        return true;
    }

    private int getMaxDivisor(int number) {
        if (number == 1) {
            return 0;
        }

        int result = 1;

        for (int i = 2; i <= Math.sqrt(number); i++) {
            if (number % i == 0 && number / i <= 10000000) {
                result = number / i;
                break;
            }
        }

        return result;
    }
}

 

참고자료

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