baekjoon. 분해합

풀이

브루트 포스 문제이다 보니 무식하게 시도했다

처음에 문제를 제대로 읽지 않고 백준에서 푼 문제인 셀프 넘버 처럼 생성자의 생성자를 찾아가는 줄 알고 헤딩을 좀 했다

4673번: 셀프 넘버

그냥 분해합을 구하는 함수를 하나 생성하고 216까지 반복문을 돌려가며 216이 만들어지는 첫 수를 반환하면 그게 제일 작은 생성자다

구현

1번째

const input = 216;
// const input = Number(require("fs").readFileSync("/dev/stdin").toString());


const check = Array(input+1).fill(0).map((_,i)=>i);

function calDeSum(num) {
    const arr = num.toString().split('').map(v=>Number(v));
    return arr.reduce((acc,v)=> acc + v ,num);
}


console.log(check.filter((v,i)=> (input === calDeSum(v)) && i)[0] || 0);

지금 보니까 굳이 배열을 만들어 돌릴 필요 없이 for문하나를 돌리는 게 나았겠다는 생각이 든다

이렇게 구현하고 보니 무슨 메모리가 500000에 속도가 1000m/s를 넘겨서 백준 맞힌 사람 리스트이 끝에서 3번째였다

풀어도 푼게 아닌 것 같아서 검색을 좀 해봤는데 역시나 알고리즘에 문제가 있었다

---

풀이

기본적인 골자는 똑같지만 1부터 input값 까지 분해합을 구할 필요가 없다는 걸 알았다

숫자가 2자리라고 한다면 이 수의 분해합은 암만 커도 117 즉, 99 + 18을 넘기지 못하는 것

그렇다면 입력받은 수 n이 3자리 수라면 n - 27(3 * 9{자릿수 하나당 9} 부터 n-1 까지 분해합을 구하면 되는 것이다

이를 바탕으로 구현해봤다

2st

const input = Number(require("fs").readFileSync("/dev/stdin").toString());

const numArr = input.toString().split('');

const deSumRange = input - numArr.length*9;


console.log(solution(deSumRange,input) || 0);

function solution(range, num){
    for(let i= range; i<num; i++){
        if(calDeSum(i) ===num) {
            return i;
        }
    }
}
function calDeSum(num) {
    const arr = num.toString().split('').map(v=>Number(v));
    return arr.reduce((acc,v)=> acc + v ,num);
}

생성자가 없을 때 0을 출력하게 하는게 조금 깔끔하지 못해서 생성자를 구하는 로직을 함수안에 넣어놓고

리턴값을 받아 유효하면 리턴값을 그렇지 못하면 0을 출력하게 했다