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

https://school.programmers.co.kr/learn/courses/30/lessons/12923#

프로그래머스

  길이가 1,000,000,000(10억) 인 블록 각각에 숫자를 부여하되, 다음 조건을 만족한다.

• 숫자의 범위는 1 ~ 10,000,000(1천만) 이다.
• 숫자 N은 2 * N, 3 * N ... 블록에 부여될 수 있으며, 작은 숫자에서 큰 숫자 순서로 블록을 덮어쓸 수 있다. 예를 들어 4번째 블록에 숫자 1이 부여되더라도, 이후 숫자 블록 2에 의해 갱신될 수 있다. 즉, 조건을 만족하는 경우 더 큰 숫자로 갱신하게 된다.

 대충 숫자를 봐도 알겠지만, 이 문제는 1부터 시작하여 순서대로 배열을 채운다는 발상으로는 풀 수 없다. 따라서 각 타일에 채워지는 숫자들의 규칙성을 따져봐야 한다.

 우선 예시의 숫자 대응 관계를 살펴보자.

1	2	3	4	5	6	7	8	9	10
0	1	1	2	1	3	1	4	3	5

  정말 대충 살펴봐도 숫자가 소수인 타일은 최대 숫자가 1로 칠해지고, 짝수는 자신의 절반 값이 칠해진다. 이때 특정 타일에 숫자가 부여되기 위한 조건을 다시 한번 생각해보자. 특정 타일에 숫자가 부여되려면 타일의 숫자 = k * N이 되어야 한다. 자기 자신은 절대 타일에 부여될 수 없으므로, 필연적으로 현재 타일에 부여되는 숫자 k는 타일의 숫자 입장에서 가장 큰 약수가 된다. 다른 값을 모두 덮어쓰기 때문이다.

타일에 배치되는 숫자들

 위 조건까지를 나타낸 코드는 다음과 같다.

function getBigSosu(n) {
    if(n == 1) {
        return 0;
    }
    for(let i = 2; i <= Math.trunc(Math.sqrt(n); i++) {
        if(n % i === 0) {
            return Math.round(n / i);
        }
    }
    return 1;
}
// 잘 보면 k가 1000 0000 까지라는 조건이 있음...

function solution(begin, end) {
    const arr = [];
    for(let i = begin; i <= end; i++) {
        arr.push(getBigSosu(i));
    }
    return arr;
}

// n -> n2 n3 n4 ... 기존 설치된 블록은 빼고 새로운 걸로 넣기
// 1부터 증가시키면서 넣기
// 10억번이라 숫자마다 넣기는 부담스럽.

  결국 각 숫자에 대해 약수를 얻는 문제이므로, 해당 숫자의 제곱근보다 작거나 같은 범위에서 1이 아닌 가장 작은 약수 m을 구하면 현재 숫자 X에 대해 2번째로 큰 약수인 X/m을 구하면 된다. 만약 이러한 약수를 찾을 수 없다면 일반적인 소수 판별 조건과 같아지므로 1을 반환한다. 여기서 멈추면 66% 정도의 정확도가 나온다.

제시된 코드에 대해 출력된 결과

 처음에는 소수점 자리가 잘못 나왔나 생각했다. 자바스크립트의 원시 자료형인 number은 정수와 실수의 구분 없이(실수로 퉁침) 값을 가지니까, 너무 큰 수를 나누려고 해서 오류가 발생했을지도 모르겠다는 생각을 했었다. 사실 예전에도 trunc와 round 차이 때문에 틀리는 문제도 봤기 때문에 더더욱 그렇게 생각했다.

 그렇지만 이번 문제는 그런 종류는 아니다. 숫자는 10,000,000보다 작다는 조건을 아직 처리하지 않았기 때문이다. 이 문제를 프로그래머스에서 접하면 10억과 1천만이 상당히 가까운 위치에서 설명되어 있어서 약간 난독이 올 수 있다. 아무튼 이 조건을 처리하기 위해 추가적인 동작을 생각해보자.

 특정 블록에 적히는 숫자는 반드시 10,000,000보다 작거나 같다. 이전 사고방식에서는 1이 아닌 가장 작은 약수를 발견하면 해당 약수와 짝을 이루는 2번째로 큰 값을 반환하는 것으로 생각했었는데, 1천만 이하라는 조건이 생기면 달라진다. 1천만을 초과하는 약수의 경우 해당 블록에 사용할 수 없으므로 넘기는 조건이 필요하다.

 한가지 조건이 더 있다. 만약 작은 값만 계속 봤고, 대응되는 값들이 모두 1천만을 넘기는 상황에서 while문 끝에 도착하는 경우는 어떨까? 이 경우 가장 큰 값은 작은 범위에서 가장 큰 약수가 블록에 지정된다. 그림으로 보면 다음과 같다.

값이 선택되는 경우들

1. 1천만이 넘지 않는 큰 범위의 값이 존재하는 경우 해당 값을 선택한다.
2. 1천만보다 작은 큰 범위 값이 존재하지 않는다면 작은 범위에서 가장 큰 값을 선택한다.
3. 작은 범위의 값이라도 어차피 1천만을 넘을 수 없으므로 root(N)과 1천만 중 작은 값으로 순회한다.

3번 조건은 현재 문제에서 의미가 없다. 10억에 루트를 씌우면 3만 정도의 수가 나오므로, 최대 순회 횟수는 많아봐야 3만대에서 멈춘다. 따라서 이 조건 자체는 무시해도 된다. 다만 경 단위의 숫자가 나온다면 의미가 있을 것 같긴 하다.

 위에서 2번 조건을 만족하기 위해서는 큰 약수를 찾을 때 도달한 작은 범위의 약수를 기억하고 있어야 한다. 이는 for문을 돌면서 약수 조건을 만족할 때마다 갱신하면 된다. 이러한 조건을 만족한 코드는 다음과 같다.

function getBigSosu(n) {
    if(n == 1) {
        return 0;
    }
    let smallsosu = 0;
    for(let i = 2; i <= Math.ceil(Math.sqrt(n)); i++) {
        if(n % i === 0) {
            const val = Math.round(n / i);
            if(val > 10000000) {
                smallsosu = i;
                continue;
            } else {
                return val;
            }
        }
    }
    return smallsosu ? smallsosu : 1;
}
// 잘 보면 k가 1000 0000 까지라는 조건이 있음...

function solution(begin, end) {
    const arr = [];
    for(let i = begin; i <= end; i++) {
        arr.push(getBigSosu(i));
    }
    return arr;
}

// n -> n2 n3 n4 ... 기존 설치된 블록은 빼고 새로운 걸로 넣기
// 1부터 증가시키면서 넣기
// 10억번이라 숫자마다 넣기는 부담스럽.
// 구간 크기는 기껏해야 5000이니까 가능은 할듯

100점 나온 결과

약수 판별까지는 별로 어렵지 않았는데, 난독 이슈가 있어서 긴가 민가 했던 것 같다.