[BAEKJOON]4673番セルフサービス番号

4673番セルフサービス番号
質問:https://www.acmicpc.net/problem/4673
質問する
セルフサービス番号は1949年にインドの数学者D.R.Kaprekarによって命名された.正の整数nについて、d(n)がnおよびnの各ビット数の関数を定義する.例えば、d(75)=75+7+5=87である.
正の整数nが与えられると、その数からn、d(n)、d(d(n)、d(d(d(n))、...無限数列を生成できます.
たとえば、33で始まると、次の数字は33+3+3=39、次の数字は39+3+9=51、次の数字は51+5+1=57となります.このようにして、次の数の列を生成できます.
33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...
nをd(n)の生成者と呼ぶ.上の数列において、33は39の生成者、39は51の生成者、51は57の生成者である.生成者が1つより多い場合もあります.例えば、101には2つの構造関数(91および100)がある.
生成されていない数字を自動番号と呼びます.100未満のセルフサービス番号は全部で13個です.1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97
10000以下のセルフ・サービス番号を出力するプログラムを作成します.
入力
入力していません.
しゅつりょく
10000以下の自己符号を行ごとに1つ追加する順序で出力します.
に答える

 let solResult = "";
// 원하는 범위까지 수열을 만드는 함수 d(n)
 function d(n, limit, array) {
   let N = String(n);
   let result = Number(n);
   if (result > limit) {
     return;
   }
   for (let i = 0; i < N.length; i++) {
     result += Number(N[i]);
   }
   array.push(result);
   d(result, limit, array);
 }

// 셀프넘버가 아닌 배열을 만들고 이를 1 ~ 범위까지의 배열과 비교
 function solution(number) {
   let array = [...Array(number)].map((a, i) => i + 1);
   let noSelfNumber = [];
   for (let i = 1; i < array.length; i++) {
     d(i, array.length, noSelfNumber);
   }
   for (let i = 0; i < array.length; i++) {
     if (noSelfNumber.indexOf(array[i]) === -1) {
       solResult += array[i].toString();
       solResult += "\n";
     }
   }
   console.log(solResult);
 }
 solution(10000);

これは私が初めて考えた解題方法です.制限範囲への呼び出しを続行した後、まず、数列を生成するd(n)関数が宣言され、1から範囲までの数値に対してd(n)を実行することができる.結果をnoSelfNumberという配列に入れ、1から範囲(10000)の配列と比較した.
両者を比較する場合、この数字がnoSelfNumberの配列になければ自動番号であるため、出力可能である.
結果は予想通り、よく撮れました.出てきたけど…😮‍💨 演算時間を全く考慮していない無知な方法です.上記の状況を考慮すると、1から10000までの数字はd(n)を使用し、各d(n)も範囲に再呼び出され続けるため、長い時間がかかる.だから白俊もタイムアウトした.
数回の試みの結果,再帰関数を用いる必要はないと結論した.再帰関数を使用して1から範囲まで数値を繰り返すと、意味のない繰り返しが続きます.1から始まる数列(1,2,4,8,16...)の場合、2から始まる数列(2、4、8、16…)または4から始まる数列(4、8、16、...)との状況が繰り返されていることがわかります.一言でこのように和音を作ると叱られるよ.🥵

// 다시 작성한 코드
// 재귀를 없애고 한번만 실행되는 d(n) 함수를 선언
function d(n) {
  let N = String(n);
  let result = Number(n);
  for (let i = 0; i < N.length; i++) {
    result += Number(N[i]);
  }
  return result;
}

// d(n)의 결과는 셀프넘버가 아니므로 false를 넣음.
function solution(range) {
  let selfNumber = [...Array(range)].map(() => true);
  for (let i = 1; i < range; i++) {
    selfNumber[d(i)] = false;
    if (selfNumber[i]) {
      console.log(i); // true인 index 출력
    }
  }
}

solution(10000);

上のコードはコミットされたコードを書き換えます.最初のコードよりも高速な演算速度を表示します.
関数d(n)を宣言するとともに、再帰関数が削除される.いずれにしても1からd(n)が実行されるため、再帰関数によって不要な重複要素を作成する必要はありません.solution()の場合、selfNumber配列を作成し、その値をtrueにすべて入れます.その後、d(n)関数を繰り返し文で呼び出し、結果値のindexにfalseを加えることで、自作番号ではない数字を区別することができる.
最後にtrue値を有するindexを出力すると、所望の結果値が得られる.
この問題を解く過程で、時間の複雑さを考え始めました.上の2つのコードの時間差が明らかで、驚きました.初期コード付きのサービスが発売されたらどうなりますか?ユーザーのネガティブなフィードバックが殺到する可能性があります.機能の正常な動作だけでなく、効率とメモリの浪費を考慮したコードを作成する必要があります.