문제 링크

문제 간단 해석

해당하는 자리에 숫자 블록이 설치되는데, 두 번째 최대약수를 찾아내면 된다. 복병은, 길이가 1,000,000,000(십억)인 도로에 1번 블록부터 시작하여 10,000,000(천만)번 블록까지만 규칙대로 설치한다는 것.. 문제를 잘 읽고 풀이해야 한다.

Java

풀이 코드

class Solution {
    public int[] solution(long begin, long end) {
        int first = (int)begin;
        int last = (int)end;
        int[] answer = new int[last - first + 1];
        
        for (int now = first; now < last + 1; now++) {
            answer[now - first] = 1;
            
            for (int div = 2; div <= Math.floor(Math.sqrt(now)); div++)
                if (now % div == 0 && now / div <= 10000000) {
                    answer[now - first] = now / div;
                    break;
                }
        }
        
        if (first == 1)
            answer[0] = 0;
        
        return answer;
    }
}

해석

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

begin, end의 범위는 1,000,000,000(십억)이하의 자연수이기 때문에 굳이 long으로 할 필요가 없다. 따라서 int형으로 형변환한 first, last로 문제를 풀기로 하였다.

for (int now = first; now < last + 1; now++) {
    answer[now - first] = 1;
    
    for (int div = 2; div <= Math.floor(Math.sqrt(now)); div++)
        if (now % div == 0 && now / div <= 10000000) {
            answer[now - first] = now / div;
            break;
        }
}

first부터 last까지 차례로 거쳐가는 now를 선언, answer에 기본적으로 1을 넣는다. 모든 자연수는 1을 약수로 지니기 때문.
값을 나눌 객체인 div를 선언, 범위는 현재값의 제곱근을 내림한 값까지이다.
2번째 최대약수를 구해야 하는 것이므로 시작값은 2.
만약 now가 div로 나머지없이 잘 나눠지고, 나눈 값이 10000000보다 같거나 작아 문제의 조건에 맞다면 해당 값을 답으로 넣어주고 for문을 탈출한다.

if (first == 1)
    answer[0] = 0;

return answer;

모든 자연수가 1을 약수로 지니지만, 어디까지나 2번째 최대약수를 출력해야 하는 것이기 때문에 시작이 1인 경우는 answer에 0을 넣어준다.
그 후 반환.

Python

풀이 코드

import math

def solution(begin, end):
    num = [0] * (end - begin + 1)
        
    for n in range(begin, end + 1):
        idx = n - begin
            
        for d in range(2, int(math.sqrt(n)) + 1):
            if n % d == 0 and n // d <= 10000000:
                num[idx] = n // d
                break
        else:
            if n == 1:
                continue
                
            num[idx] = 1
    
    return num

해석

num = [0] * (end - begin + 1)
        
for n in range(begin, end + 1):
    idx = n - begin

답을 반환할 배열 생성.
begin부터 end까지 차례로 거쳐가는 n 선언, 배열에서의 순서를 나타낼 idx 선언.

for d in range(2, int(math.sqrt(n)) + 1):
    if n % d == 0 and n // d <= 10000000:
        num[idx] = n // d
        break
else:
    if n == 1:
        continue
        
    num[idx] = 1

n이 d로 잘 나누어떨어지고, 그 값이 10000000보다 작다면 답을 기록한다.
만약 답이 기록되지 않는 수라면 1 혹은 소수인데, 1인 경우는 넘기고 소수인 경우는 1을 기록한다.

여담

처음 풀 때 길이가 1,000,000,000(십억)인 도로에 1번 블록부터 시작하여 10,000,000(천만)번 블록까지를 제대로 보지 못 해서 쓸데없이 시간을 날렸던 기억이 있다.
문제를 잘 읽자..