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

Link | 프로그래머스 12923번 문제 : 숫자 블록

📌 About

문제 이해 자체는 쉬운 문제이다.

N부터 M까지의 수가 주어졌을 때 (N <= M) 각각의 수를 두 번째로 큰 약수로 바꾸면 된다.

다만, 1은 약수가 하나기 때문에 0으로 변환한다.

또한 약수는 10,000,000을 넘어서는 안된다.

📌 Solution

Step 1. 형변환

사실 주어진 long type 변수 begin과 end는 int 형을 다루어도 문제가 없다.

그렇기 때문에 앞으로의 편의를 위해 형변환을 한다.

int from = (int) begin;
int to = (int) end;

Step 2. Block 탐색

이제 from부터 to까지 탐색하면서 해당 변수의 변환값을 구하면 된다.

이 때 블록의 수가 1이면 0으로 변환한다.

for (int n = from; n <= to; n++) {
	if (n == 1) // 0 저장
    // 약수 구하기   
}

Step 3. 약수 구하기

1은 모든 수가 약수로 가지고 있다.

그렇기 때문에 두 번째로 큰 약수는 2부터 나누어서 구한다.

이때 나눈 값이 10,000,000보다 크면 안된다.

for (int d = 2; d <= Math.sqrt(n); d++) {
    if (n % d == 0) {
        if (n / d <= 10_000_000) // n / d 저장;
    }
}

📌 Code

GitHub Repository

Java Stream을 통해 짧게 작성이 가능하다.

여기서 주의해야 할 점은 div 값을 설정해야 한다는 것이다.

100,000,014 ~ 100,000,016의 경우를 생각하면 필요성을 알 수 있다.

class Solution {
    public int[] solution(long begin, long end) {
        return IntStream.rangeClosed((int) begin, (int) end).map(n -> {
            if (n == 1) return 0;
            int div = 1;
            for (int d = 2; d <= Math.sqrt(n); d++) {
                if (n % d == 0) {
                    div = d;
                    if (n / d <= 10_000_000) return n / d;
                }
            }
            return div;
        }).toArray();
    }
}