[12923] 숫자 블록

✔ 숫자 블록

[프로그래머스 12923]

문제 분석하기

begin과 end 사이의 값들에 대해서 

소수인 경우 1, 소수가 아닌 경우 약수 중에서 자기 자신을 제외한 최댓값으로 갱신하도록 함

블록
1번째 (1)	2번째 (1, 2)	3번째 (1, 3)	4번째 (1, 2, 4)	5번째 (1, 5)	6번째 (1, 2, 3, 6)	7번째 (1, 7)	8번째 (1, 2, 4, 8)	9번째 (1, 3, 9)	10번째 (1, 2, 5, 10)
0	0	0	0	0	0	0	0	0	0
0	0 → 1 (1*2 번째)	0 → 1 (1*3 번째)	0 → 1 (1*4 번째)	0 → 1 (1*5 번째)	0 → 1 (1*6 번째)	0 → 1 (1*7 번째)	0 → 1 (1*8 번째)	0 → 1 (1*9 번째)	0 → 1 (1*10 번째)
0	1	1	1 → 2 (2*2번째)	1	1 → 2 (2*3번째)	1	1 → 2 (2*4번째)	1	1 → 2 (2*5번째)
0	1	1	2	1	2 → 3 (3*2번째)	1	2	1 → 3 (3*3번째)	2
0	1	1	2	1	3	1	2 → 4 (4*2번째)	3	2
0	1	1	2	1	3	1	4	3	2 → 5 (5*2번째)
[0, 1, 1, 2, 1, 3, 1, 4, 3, 5]

손으로 풀어보기

1. 소수인 경우, 1로 갱신
2. 소수가 아닌 경우, 약수 중에서 자기 자신을 제외한 최댓값을 갱신
   • 이때 약수에 해당하는 값이 10000000보다 작다면 바로 이 값을 사용
   • 만약 10000000보다 크다면 이 블록은 사용할 수 없으므로 다른 약수 중에서 가장 큰 수를 사용
   • 예) 10이라면 2는 10의 약수이므로 5를 반환.
     이때 5는 10000000보다 작으므로 사용 가능하지만 만약 10000000보다 크다면 5보다 작은 약수인 2를 사용해야 함
3. 배열을 반환

슈도코드 작성하기

begin, end(구간을 나타내는 두 정수)
answer(구간에 깔려 있는 블록의 숫자 배열)
index(위치 저장 인덱스)
for(i -> begin부터 end까지) {
    answer[index++] = 약수의 최대값 구하기 함수(i) 
}
answer 반환

약수의 최대값 구하기 함수 {
    if(n == 1)
        0 반환
    divisor(n의 약수를 담은 리스트)
    for(i -> 2부터 Math.sqrt(n)까지) {
        if(n % i == 0) {
            divisor에 i 저장
            if(n / i의 값이 10000000보다 작거나 같다면)
                n / i 반환
        }
    }
    if(divisor가 비어있지 않다면) 
        divisor 중 가장 큰 값 반환
    1 반환
}

코드 구현하기

/**
 * 12923) 숫자_블록
 */
public class L012_12923 {
    // begin, end(구간을 나타내는 두 정수)
    public int[] solution(long begin, long end) {
        // answer(구간에 깔려 있는 블록의 숫자 배열)
        int[] answer = new int[(int) (end - begin) + 1];
        // index(위치 저장 인덱스)
        int index = 0;
        for (int i = (int) begin; i <= (int) end; i++) {
            // answer[index++] = 약수의 최대값 구하기 함수(i)
            answer[index++] = getDivisorMax(i);
        }
        // answer 반환
        return answer;
    }

    // 약수의 최대값 구하기 함수
    private int getDivisorMax(int n) {
        // 1이라면
        if (n == 1)
            // 0 반환
            return 0;
        // divisor(n의 약수를 담은 리스트)
        ArrayList<Integer> divisor = new ArrayList<>();
        for (int i = 2; i <= Math.sqrt(n); i++) {
            // n이 i로 나누어진다면
            if (n % i == 0) {
                // i는 n의 약수이므로 divisor에 i 저장
                divisor.add(i);
                // n / i의 값이 10000000보다 작거나 같다면
                if (n / i <= 10000000)
                    // 가장 큰 약수인 n / i를 바로 반환
                    return n / i;
            }
        }
        // divisor가 비어있지 않다면
        if (!divisor.isEmpty())
            // divisor 중 가장 큰 값 반환
            return divisor.get(divisor.size() - 1);
        // 약수가 없는 소수라면 1 반환
        return 1;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L012_12923 solution = new L012_12923();

        long begin = 1;
        long end = 10;

        int[] result = solution.solution(begin, end);

        System.out.println(Arrays.toString(result));
    }
}