catsridingCATSRIDING|OCEANWAVES
Challenges

프로그래머스 | Level 2 | 숫자 블록

jin@catsriding.com
Oct 25, 2024
Published byJin
999
프로그래머스 | Level 2 | 숫자 블록

Programmers | Level 2 | 숫자 블록

Problems

󰧭 Description

그렙시에는 숫자 0이 적힌 블록들이 설치된 도로에 다른 숫자가 적힌 블록들을 설치하기로 하였습니다. 숫자 블록을 설치하는 규칙은 다음과 같습니다.

블록에 적힌 번호가 n 일 때, 가장 첫 블록은 n * 2번째 위치에 설치합니다. 그 다음은 n * 3, 그 다음은 n * 4, ...위치에 설치합니다. 기존에 설치된 블록은 빼고 새로운 블록을 집어넣습니다.

블록은 1이 적힌 블록부터 숫자를 1씩 증가시키며 순서대로 설치합니다. 예를 들어 1이 적힌 블록은 2, 3, 4, 5, ... 인 위치에 우선 설치합니다. 그 다음 2가 적힌 블록은 4, 6, 8, 10, ... 인 위치에 설치하고, 3이 적힌 블록은 6, 9, 12... 인 위치에 설치합니다.

이렇게 3이 적힌 블록까지 설치하고 나면 첫 10개의 블록에 적힌 번호는 [0, 1, 1, 2, 1, 3, 1, 2, 3, 2]가 됩니다.

그렙시는 길이가 1,000,000,000인 도로에 1부터 10,000,000까지의 숫자가 적힌 블록들을 이용해 위의 규칙대로 모두 설치 했습니다.

그렙시의 시장님은 특정 구간에 어떤 블록이 깔려 있는지 알고 싶습니다.

구간을 나타내는 두 정수 begin, end 가 매개변수로 주어 질 때, 그 구간에 깔려 있는 블록의 숫자 배열을 return하는 solution 함수를 완성해 주세요.

 Constraints

  • 1 ≤ beginend ≤ 1,000,000,000
  • end - begin ≤ 5,000

󰦕 Examples

beginendresult
110[0, 1, 1, 2, 1, 3, 1, 4, 3, 5]

Solutions

󰘦 Code

Solution.java
import java.util.*;

class Solution {
    public int[] solution(long begin, long end) {
        // 구간의 길이를 계산하여 결과 배열 초기화
        int length = (int) (end - begin + 1);
        int[] numbers = new int[length];  // 구간 내 블록 숫자를 저장할 배열
        
        // 구간의 각 위치에 대해 블록 값을 계산
        for (long i = begin; i <= end; i++) {
            int idx = (int) (i - begin);  // 현재 블록의 위치 인덱스를 구함
            numbers[idx] = calcLargestDiv(i);  // 각 위치의 블록 값을 계산하여 저장
        }
        
        return numbers;  // 구간 내 블록 숫자가 저장된 결과 배열 반환
    }
    
    private int calcLargestDiv(long block) {
        // 블록이 위치 1일 경우 특별히 0을 반환 (규칙에 따라 값이 없음을 의미)
        if (block == 1) return 0;
        
        int largestDiv = 1;  // 초기값을 1로 설정 (10,000,000 초과 시 반환할 최소값)
        
        // 최대 약수를 찾기 위해 블록의 제곱근까지만 탐색하여 효율성을 높임
        for (long i = 2; i <= Math.sqrt(block); i++) {
            // `i`가 `block`의 약수라면
            if (block % i == 0) {                
                // 해당 약수가 10,000,000 이하일 경우 즉시 반환 (최대 조건을 만족)
                if (block / i <= 10_000_000) return (int) (block / i);
                
                // 그 외의 경우, 현재 탐색된 약수 i를 임시로 저장 (후에 더 큰 약수로 갱신될 수 있음)
                largestDiv = (int) i;
            }
        }
        
        // 탐색 완료 후 가장 큰 약수를 반환 (모든 약수가 10,000,000 초과 시 1을 반환)
        return largestDiv;
    }
}

 Approaches

이 문제는 특정 구간에서 숫자 블록의 값을 구하는 문제입니다. 각 블록 위치에 가장 큰 약수를 찾아서 값을 결정해야 합니다. 따라서 효율적으로 약수를 탐색하고, 해당 구간의 블록 값을 빠르게 계산하는 것이 중요합니다.

1. 문제 분석

블록에 적힐 숫자를 결정하는 규칙은 각 위치에 대해 자신을 제외한 가장 큰 약수를 찾는 것입니다. 예를 들어, 블록 위치 n에 대해 가장 큰 약수가 k라면 해당 위치에 k가 적힙니다.

단, 블록 위치가 1인 경우는 예외로 하여 값이 0이 됩니다. 이는 1이 유일한 약수를 가지며, 다른 숫자의 배수가 될 수 없기 때문에 해당 위치에는 어떤 숫자 블록도 설치되지 않기 때문입니다. 따라서 도로의 시작 블록인 위치 1은 항상 0으로 표시됩니다.

또한 이 문제에서는 도로의 길이와 블록에 적힐 수 있는 최대 숫자가 다르다는 점에 주의해야 합니다. 블록이 설치될 위치는 최대 1,000,000,000까지 가능하지만, 블록에 적힐 수 있는 숫자는 10,000,000 이하의 약수로 제한됩니다. 따라서 각 위치에서 약수를 탐색할 때 자신을 제외한 가장 큰 약수 중 10,000,000 이하인 값이 표시됩니다. 만약 n의 모든 약수가 10,000,000을 초과하면, 해당 위치에는 1이 적히게 됩니다.

이를 통해 규칙에 따라 구간 내 블록 값을 효율적으로 계산할 수 있습니다.

2. 접근 방식

이 문제는 큰 범위의 값을 효율적으로 처리해야 하므로, 다음과 같은 단계를 통해 해결합니다.

  1. 배열 초기화: 주어진 [begin, end] 구간의 크기에 맞춰 결과 배열을 초기화합니다.
  2. 블록 값 계산: 각 위치에 대해 자신을 제외한 가장 큰 약수를 찾아서 그 값을 배열에 기록합니다. 이때, 약수는 10,000,000 이하인 값 중에서 가장 큰 값을 선택하며, 이를 통해 조건에 맞는 최적의 블록 값을 설정합니다.
  3. 최대 약수 탐색 최적화: 각 위치에서 가장 큰 약수를 구할 때, 시간 복잡도를 줄이기 위해 해당 위치의 제곱근까지만 탐색합니다. 이 과정에서 약수가 10,000,000 이하일 때만 블록의 값으로 사용하고, 모든 약수가 조건을 초과할 경우에는 1을 반환합니다.
3. 구간 배열 초기화

주어진 구간 [begin, end]의 크기를 계산하여 결과 배열을 초기화하고, 각 위치의 블록 값을 저장할 준비를 합니다.

Solution.java
int length = (int) (end - begin + 1);  // 구간의 길이 계산
int[] numbers = new int[length];  // 구간 내 블록 숫자를 저장할 배열
4. 블록 값 계산을 위한 가장 큰 약수 찾기

각 위치의 블록 값을 구하기 위해, 주어진 위치에서 자신을 제외한 가장 큰 약수를 찾습니다. 이 과정에서 제곱근까지만 탐색하여 효율성을 높이고, 약수가 10,000,000 이하일 경우 그 값을 블록 값으로 사용합니다. 만약 1인 위치라면 0으로 예외 처리합니다.

Solution.java
for (long i = begin; i <= end; i++) {
    int idx = (int) (i - begin);  // 현재 블록의 위치 인덱스
    numbers[idx] = calcLargestDiv(i);  // 각 위치의 블록 값을 설정
}

가장 큰 약수를 찾는 함수는 주어진 블록에 대해 자신을 제외한 가장 큰 약수를 반환하는 역할을 합니다. 이 함수는 효율성을 위해 약수 탐색 범위를 제곱근까지만으로 제한하여 계산을 최적화합니다. 블록이 1인 경우에는 예외적으로 0을 반환하며, 그 외의 경우 조건에 맞는 최대 약수를 찾습니다.

여기서 블록에 적힐 숫자는 10,000,000 이하의 약수만 허용되므로, 모든 약수가 10,000,000을 초과하면 1을 반환합니다. 이는 규칙상 해당 위치가 최소한으로 설치되는 블록 값을 가지도록 하기 위한 조치로, 특정 위치에 10,000,000 이하의 약수가 없는 경우 그 위치의 블록에 1을 표시합니다.

Solution.java
private int calcLargestDiv(long block) {
     // 블록이 위치 1일 경우 특별히 0을 반환 (규칙에 따라 값이 없음을 의미)
    if (block == 1) return 0;
    
    int largestDiv = 1;  // 초기값을 1로 설정 (10,000,000 초과 시 반환할 최소값)
    // 최대 약수를 찾기 위해 블록의 제곱근까지만 탐색하여 효율성을 높임
    for (long i = 2; i <= Math.sqrt(block); i++) {
        // `i`가 `block`의 약수라면
        if (block % i == 0) {                
            if (block / i <= 10_000_000) return (int) (block / i);  // 해당 약수가 10,000,000 이하일 경우 즉시 반환 (최대 조건을 만족)
            largestDiv = (int) i;  // 그 외의 경우, 현재 탐색된 약수 i를 임시로 저장 (후에 더 큰 약수로 갱신될 수 있음)
        }
    }
    
    // 탐색 완료 후 가장 큰 약수를 반환 (모든 약수가 10,000,000 초과 시 1을 반환)
    return largestDiv;
}
5. 블록의 숫자 배열 반환

이렇게 구간 내 모든 블록 값이 계산되면, 최종적으로 결과 배열 반환하여 [begin, end] 구간에 해당하는 블록 숫자 배열을 제공합니다.

Solution.java
// 구간 내 블록 숫자가 저장된 결과 배열 반환
return numbers;

󰄉 Complexity

  • TC: O(n * sqrt(m))
  • 💾 SC: O(n)

각 블록 위치에서 제곱근까지만 탐색하므로 O(sqrt(m))의 시간 복잡도를 가지며, 구간 길이가 최대 5,000이므로 최종 시간 복잡도는 O(n * sqrt(m))입니다. 공간 복잡도는 구간의 길이만큼 배열을 사용하므로 O(n)입니다.

  • Algorithm
  • Math