[프로그래머스 Lv.2] 숫자 블록(Java) - 약수

📌 핵심 요약

• 문제 재진술 — 위치 p에 남는 블록은 p의 약수 중 p 자신을 제외한 최댓값이다.
• 제약 반영 — 블록은 1,000만까지만 존재하므로 최대 약수가 그보다 크면 다음 약수를 찾아야 한다.
• 탐색 범위 — 약수는 i와 p/i가 짝을 이루므로 √p까지만 훑으면 충분하다.
• 조기 반환 — i가 커질수록 p/i는 작아지므로, 상한 이하가 되는 첫 값이 곧 정답이다.

 

목차

Programmers #12923

숫자 블록

도로 길이 10억 · 블록 번호 ≤ 1,000만 · 구간 ≤ 5,000

난이도: Lv.3

번호 n인 블록은 n×2, n×3, n×4, ... 위치에 설치된다. 블록은 1번부터 순서대로 깔리며 기존 블록을 덮어쓴다. 구간 [begin, end]에 최종적으로 깔린 블록 번호 배열을 반환한다.

풀이 과정

1. 위치 p 하나를 고정해 "여기에 놓일 수 있는 블록"을 약수로 환원한다.
2. 덮어쓰기 순서가 오름차순이므로 최댓값만 남는다.
3. √p까지 훑으며 1,000만 이하가 되는 첫 짝을 반환한다.

1 규칙을 위치 기준으로 뒤집기

지문은 블록을 기준으로 서술되어 있다. 번호 n인 블록이 n×2, n×3, ... 위치에 깔리고, n을 1부터 늘려 가며 기존 블록을 덮어쓴다. 이 서술을 그대로 따라가면 시뮬레이션을 떠올리게 되는데, 도로 길이가 10억이라 불가능하다.

그래서 관점을 뒤집었다. 블록이 아니라 위치 p 하나를 고정하고, 여기에 어떤 블록들이 거쳐 갔는지 물었다.

블록 n이 위치 p에 놓이려면 p = n × k이면서 k ≥ 2여야 한다. 첫 설치 위치가 n×2부터이기 때문이다. 이 조건을 정리하면 이렇게 된다.

n은 p의 약수이면서, p 자신은 아니다.

p = 12의 추적

진행	놓이는 블록	근거	위치 12의 상태
n = 1	1	12 = 1 × 12	1
n = 2	2	12 = 2 × 6	2
n = 3	3	12 = 3 × 4	3
n = 4	4	12 = 4 × 3	4
n = 6	6	12 = 6 × 2	6
n = 12	해당 없음	12×2 = 24부터 시작	6

n이 커지는 순서로 덮어쓰므로 마지막에 남는 것은 후보 중 최댓값이다.

그리고 n = 12는 자기 자리에 놓이지 않으므로 후보에서 빠진다. 즉 구할 값은 p의 최대 약수이고,

이는 p ÷ (p의 가장 작은 소인수)와 같다. 가장 작은 값으로 나눌수록 몫이 커지기 때문이다.

예시 검증

begin = 1, end = 10일 때 기대 출력은 [0, 1, 1, 2, 1, 3, 1, 4, 3, 5]다.

p	자신을 제외한 약수	최댓값	결과
1	없음	—	0
2	1	1	1
4	1, 2	2	2
6	1, 2, 3	3	3
8	1, 2, 4	4	4
9	1, 3	3	3
10	1, 2, 5	5	5

위치 1이 0인 이유는 n × 2 = 1을 만족하는 블록이 존재하지 않아서다. 소수 위치는 약수가 1뿐이라 항상 1이 남는다.

2 규모 판단

항목	값	함의
도로 길이	10억	전체 배열 생성 불가
구간 길이	최대 5,001	위치별 독립 계산이 가능
위치 p	최대 10억	√p ≈ 31,623까지 탐색 허용
블록 번호	최대 1,000만	답에 상한이 걸린다

두 번째와 세 번째 줄을 곱하면 약 1.6억이다. 상한으로만 보면 아슬아슬하지만, 실제로는 대부분의 위치가 몇 번 만에 끝난다는 점을 뒤에서 확인했다.

3 약수 탐색 설계

약수는 i와 p/i가 짝을 이루므로 √p까지만 훑으면 전부 확인된다. 여기에 관찰 하나를 더했다.

i가 커질수록 짝인 p/i는 작아진다.

우리가 원하는 것은 상한(1,000만) 이하에서 가장 큰 값이다. 따라서 i를 2부터 올리며 처음으로 p/i ≤ 1,000만이 되는 순간이 곧 정답이고, 더 볼 필요 없이 반환할 수 있다.

ℹ️

조기 반환이 성립하는 이유

i가 증가하면 p/i는 단조 감소한다. 즉 조건을 만족하는 첫 값이 후보 중 최댓값이고, 이후에 나오는 값들은 모두 그보다 작다.

4 코드

 

Java — Solution.java

class Solution {
    public int[] solution(long begin, long end) {
        int b = (int) begin;
        int e = (int) end;
        int[] answer = new int[e - b + 1];

        for (int i = b; i <= e; i++) {
            answer[i - b] = getMaxBlock(i);
        }

        return answer;
    }

    private int getMaxBlock(int n) {
        if (n == 1) return 0;

        int maxBlock = 1; // 기본적으로 자기 자신 외 가장 작은 약수는 1

        for (int i = 2; (long) i * i <= n; i++) {
            if (n % i == 0) {
                // n / i가 10,000,000 이하인 경우, 이 값이 나누어떨어지는 가장 큰 약수
                if (n / i <= 10_000_000) {
                    return n / i;
                }

                // n / i가 10,000,000을 초과하면 i(더 작은 약수)를 후보로 저장해두고 계속 탐색
                maxBlock = i;
            }
        }

        return maxBlock;
    }
}

복잡도

위치는 최대 5,001개이고 각 위치는 최대 √p ≈ 31,623번 돈다. 상한을 곱하면 약 1.6억이지만, 실제 반복 횟수는 훨씬 적다.

위치 유형	반복 횟수	5,000개 중 대략
짝수	1회 (i=2에서 즉시 반환)	2,500개
3의 배수	2회	800개
소수	약 31,623회	240개

끝까지 도는 것은 소수뿐이고, 10억 부근에서 5,000개 중 소수의 개수는 대략 5000 / ln(10⁹) ≈ 240이다. 전체 연산은 1천만 회 미만이라 여유롭게 통과한다.

5 실수했던 부분

지문의 중간 상태 배열을 최종 답으로 읽었다

원인. 문제 설명에 [0, 1, 1, 2, 1, 3, 1, 2, 3, 2]라는 배열이 등장한다. 처음에는 이것이 begin=1, end=10의 정답이라고 판단했다. 그런데 입출력 예의 결과는 [0, 1, 1, 2, 1, 3, 1, 4, 3, 5]로 다르다. 두 배열을 같은 것으로 놓고 규칙을 역산하려 하니 앞뒤가 맞지 않았다.

해결. 지문을 다시 읽어 보니 앞의 배열은 블록 3번까지만 깔았을 때의 중간 상태였다. 이후 블록 4와 5가 8번, 10번 자리를 덮어써서 최종 배열이 된다. 규칙 설명용 예시와 정답을 구분하지 않은 것이 원인이었다.

⚠️

두 배열의 차이

8번 위치: 중간 상태 2 → 최종 4 (블록 4가 덮어씀). 10번 위치: 중간 상태 2 → 최종 5 (블록 5가 덮어씀).

블록 번호 상한을 반영하지 않을 뻔했다

원인. "최대 약수를 구한다"까지 정리한 뒤 바로 코드를 쓰려 했다. 그런데 블록은 1,000만까지만 존재하고 도로는 10억이다. 이 차이를 놓치면 존재하지 않는 블록 번호를 답으로 내게 된다.

예를 들어 p = 30,000,000의 최대 약수는 15,000,000인데, 그런 번호의 블록은 설치된 적이 없다. 실제로는 그다음 약수인 10,000,000이 답이다.

i	n / i	판정	동작
2	15,000,000	상한 초과	maxBlock = 2, 계속
3	10,000,000	통과	반환

해결. 조건을 "p보다 작은 최대 약수"가 아니라 "p보다 작고 1,000만 이하인 최대 약수"로 다시 적었다. 구간이 1,000만 이하에 있으면 이 제약이 무해하기 때문에, 작은 값으로만 테스트하면 끝까지 드러나지 않는 종류의 조건이었다.

루프 종료 시 1을 반환하려 했다

원인. 조기 반환에 걸리지 않고 루프가 끝나는 경우는 소수뿐이라고 판단해, 마지막 줄을 return 1;로 쓰려 했다. 그러나 반례가 있다.

p = 999,999,998 = 2 × 499,999,999를 보자. i = 2에서 나누어떨어지지만 짝인 499,999,999가 상한을 넘는다. 이후 √p까지 다른 약수를 찾지 못하고 루프가 끝난다. 이때 정답은 1이 아니라 2다.

해결. maxBlock = i로 후보를 저장해 두고 루프 종료 시 그 값을 반환하도록 했다. 큰 소수와 짝을 이루는 작은 약수가 답이 되는 경우를 담당하는 줄이다.

🚨

이 줄이 없으면 놓치는 케이스

p가 "작은 수 × 매우 큰 소수" 꼴일 때. 짝이 상한을 넘어 조기 반환에 걸리지 않고, 다른 약수도 없어 루프가 끝난다. maxBlock 없이는 1을 반환하게 된다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.