코딩테스트/Java

[programmers/java] 숫자 블록_가장 큰 약수, Math.sqrt

zyin 2025. 7. 1. 23:54

1. 개요

본 문서는 주어진 정수 구간 [begin, end]에 대해 각 위치에 설치될 숫자 블록의 값을 계산하는 알고리즘을 설명한다. 해당 문제는 특정 규칙에 따라 도로 위 위치마다 하나씩 블록을 설치하며, 각 블록에 적히는 숫자는 해당 위치값의 특정 조건을 만족하는 약수에 의해 결정된다.

2. 문제 정의

  • 도로는 1부터 1,000,000,000까지의 정수 위치로 구성된다.
  • 각 위치 n에는 블록 하나가 설치되며, 해당 블록에 적히는 숫자는 다음 규칙에 의해 결정된다:
    1. n == 1인 경우, 블록은 설치되지 않으며 숫자 0이 반환된다.
    2. n > 1인 경우, n의 자기 자신을 제외한 약수 중에서 가장 큰 값을 구한다.
    3. 단, 해당 약수 d에 대해 n / d ≤ 10,000,000일 때만 유효하다.
    4. 위 조건을 만족하는 약수가 존재하지 않을 경우, 기본값 1이 사용된다.

3. 알고리즘 설계

3.1 전체 흐름

  • 입력: 구간 [begin, end] (1 ≤ begin ≤ end ≤ 1,000,000,000, end - begin ≤ 5,000)
  • 출력: int[] 타입의 정수 배열로, 각 위치에 설치된 블록의 숫자를 순서대로 포함한다.

3.2 처리 절차

  1. end - begin + 1 크기의 배열을 생성한다.
  2. begin부터 end까지 각 위치값 n에 대해 아래의 절차를 수행한다:
    • n == 1인 경우, 값 0을 할당한다.
    • n > 1인 경우, getMaxDivisor(n) 함수를 호출하여 적절한 블록 값을 계산한다.

4. 핵심 함수: getMaxDivisor(long n)

본 함수는 위치값 n에 대해 조건을 만족하는 가장 큰 약수를 계산한다. 다음과 같은 방식으로 구현된다:

  1. n == 1인 경우 예외적으로 0을 반환한다.
  2. i = 2부터 i * i <= n까지 반복하며 약수 후보를 탐색한다.
  3. i가 n의 약수이면, 약수 쌍 (i, n / i)를 얻는다.
  4. 쌍 중 n / i ≤ 10,000,000이면 해당 값을 즉시 반환한다.
  5. 아니라면 i ≤ 10,000,000인 경우에는 현재까지의 최대값과 비교해 갱신한다.
  6. 반복을 마치면 최종적으로 max 값을 반환한다.

5. 구현 코드

import java.util.*;

class Solution {
    public int[] solution(long begin, long end) {
        int size = (int)(end - begin + 1);
        int[] answer = new int[size];
        
        for (long i=begin;i<=end;i++){
            int idx = (int) (i-begin);
            answer[idx] = number((int)i);
        }
        
        return answer;
    }
    
    public int number(int num){
        if (num <= 1) return 0;
        double limit = Math.sqrt(num);
        int answer = 1;
        
        for (int i=2; i<= limit ; i++){
            int other = num / i;
            if (num % i == 0){
                if (other <= 10_000_000) return other;
                if (i <= 10_000_000) answer = Math.max(answer, i);
                else break;
            }
        }
        return answer;
    }
}

6. 성능 분석

6.1 시간 복잡도

  • 각 수 n에 대해 최대 √n만큼 반복하므로, 한 숫자당 최대 수천 회 연산으로 제한된다.
  • 전체 반복 횟수는 end - begin ≤ 5,000이므로 총 연산량은 약 5,000 × √1,000,000,000 ≈ 500만 수준이다.
  • 이는 Java의 기본 시간 제한 내에서 충분히 통과 가능하다.

6.2 소수 처리

  • n이 소수일 경우 약수 후보가 없기 때문에 루프가 끝까지 진행된다.
  • 그러나 루프 상한을 √n으로 제한함으로써 소수에 대해서도 연산량이 제한된다.