알고리즘 풀이 4)1-3 (완전탐색-블루투포스)

이날따라 문제가 버거워서 풀기가 너무 힘들었다ㅜ0ㅜ

 

Section4_1번: 자리수의 합

------------강의 풀이1 (숫자형-자리수 나눠서 분리)---------------

function solution4_1(arr: number[]) {
    let answer=0; 
    let max=Number.MIN_SAFE_INTEGER;
    for(let num of arr){
      let sum=0, tmp=num; //원본 숫자는 변형되지 않도록 tmp에 깊은 복사
      while(tmp){ //tmp가 0이 아닌 수이면 ture, 0이면 false
          sum+=(tmp%10);
          tmp=Math.floor(tmp/10);
      }
      if(sum>max){
          max=sum; //sum에 들어간건 복사해서 변형한 tmp
          answer=num; //답에 넣을건 원본인 num
      }
      else if(sum===max){
          if(num>answer) answer=num; 
      }
    }
    return answer;
}
console.log(solution4_1([128, 460, 603, 40, 521, 137, 123]));

 

------------강의 풀이2 (문자형-쪼개고 형변환)---------------

function solution4_1(arr: number[]) {
    let answer=0;
    let max=Number.MIN_SAFE_INTEGER;
      for(let x of arr){
        let sum=num.toString().split('').reduce((a, b)=>a+Number(b), 0); //문자+숫자->숫자
        if(sum>max){
          max=sum;
          answer=num;
        }
        else if(sum===max){
          if(num>answer) answer=num;
        }
      }
      return answer;
}
console.log(solution4_1([128, 460, 603, 40, 521, 137, 123]));

혼자 풀어볼땐 자릿수의 합이 같은 숫자가 나오면 원본숫자로 비교를 어떻게 하나 고민이였다.

합이 같은게 두개가 아니라면? 인덱스 구해서 원래숫자비교하고? 다시 인덱스 구해야하나?

풀이)  for문 안에서 깊은 복사를 한 변수를 선언한 뒤에 자리수 합은 복사한 변수로, 반환할 값은 원본값으로 반환하는 방법을 사용했다.

• let answer; 으로 선언만 하고 else if문에서 answer과 num을 비교했더니 할당이 되지 않은 값이라 오류가 떴는데 JS로는 오류가 뜨지 않았다. 

     -> js에서 변수 선언 후, 할당이 되지 않으면 undefined로 초기화 된 상태이다.

         이때 undefined는 비교연산자를 사용한 비교가 불가능하다(숫자형 변환시 NaN이라서 비교 결과는 언제나 false반환.)

         js 풀이에서는 false반환하는 원리를 이용해 if문 활용이 되었지만 ts에서는 애초에 불가능한 로직이였다.

 

Section4_2번: 뒤집은 소수

 

function solution4_2(arr: number[]): any {
  let reversedArr: number[] = [];
  let answer: number[] = [];
  for (let num of arr) {
    reversedArr.push(Number(String(num).split("").reverse().join("")));
  }
  for (let num of reversedArr) {
    let isPrime = true;
    if (num !== 1) {
      for (let i = 2; i < num / 2; i++) {
        if (num % i === 0) {
          isPrime = false;
          break;
        }
      }
      if (isPrime === true) answer.push(num);
    }
  }
  return answer;
}
console.log(solution4_2([32, 55, 62, 20, 250, 370, 200, 30, 100]));

• 오랜만에 소수반별하려니 머리에 혼란이 왔던 문제.. isPrime=true/false로 숫자가 소수인지 아닌지 확인해주는 단계가 필요했다. 이렇게 단계를 한번 거치치 않고 if문에서 바로 소수를 배열에 넣을 수는 없나? 아직은 방법을 못찾았다...
• num의 약수는 절반을 넘을 수 없다고 하길래 for문 실행시간을 줄이기 위해 num/2를 해주었다. 
  • 제곱근을 사용하면 시간복잡도를 더 줄일 수 있다. -> Math.sqrt(sum)

 

 

Section4_3번: 멘토링