[Level2] 12. 55 ~ 59

in 코딩테스트 on 프로그래머스




2단계 시작! 하루에 최소 3문제, 오늘은 숫자 부시기


55. N개의 최소공배수

프로그래머스 

const gcd = (a, b) => {
  if (a < b) [a, b] = [b, a];
  while (b > 0) {
    let temp = b;
    b = a % b;
    a = temp;
  }
  return a;
};

const lcm = (a, b) => {
  return (a * b) / gcd(a, b);
};

function solution(arr) {
  let answer = 1;
  for (let i = 0; i < arr.length; i++) {
    answer = lcm(answer, arr[i]);
  }
  return answer;
}

30번 문제에서 풀었던 최대공약수, 최소공배수를 그대로 활용하는 문제였다.
유클리드 호제법은 암기를 해두는게 좋을 것 같다.
헷갈리니 다시 짚고 넘어가자


유클리드 호제법

  • 2개의 자연수의 최대공약수를 구하는 알고리즘
  • 두 개의 자연수 a, b에서 (a>b) a를 b로 나눈 나머지를 r이라 할 때, GCD(a,b) === GCD(b,r)
  • r이 0이면 그 때의 b가 최대공약수이다.
  • ex) GCD(24,16) === GCD(16, 8) === GCD(8,0) 최대공약수 = 8
  • 최소공배수 : LCM = (a * b) / 최대공약수 === (a * b) / GCD(a, b)



best 풀이

function nlcm(num) {
 return num.reduce((a,b) => a*b / gcd(a,b))  
}

function gcd(a, b) {
  return a % b ? gcd(b, a%b) : b
}

// 아래는 테스트로 출력해 보기 위한 코드입니다.
console.log(nlcm([2,6,8,14]));

원리는 동일한데 그걸 코드로 엄청 깔끔하게 잘 정리한 것 같다.
이런 센스는 도대체 어떻게 해야 얻을 수 있는거지…???!!!


56. 최솟값 만들기

programmers 

function solution(A, B) {
  A.sort((a, b) => a - b);
  B.sort((a, b) => b - a);
  return A.reduce((acc, value, index) => acc + value * B[index], 0);
}

2단계 문제를 대할 떼 사실 엄청 쫄아있었는데 이건 너무 간단했다.
이게 왜 2단계에 있지?
쫄지 말자!! 할 수 있따!!!
best 풀이와 동일함으로 best는 패스!



57. 최댓값과 최솟값

programmers 

function solution(s) {
  let temp = s.split(" ");
  temp.sort((x, y) => x - y);
  return `${temp[0] / 1} ${temp[temp.length - 1] / 1}`;
}

이주전에 한번 도전했다가 포기했던 문제인데 이제는 풀린다!!
점점 실력이 쌓이는게 느껴진다. 더더 열심히하자 🤩👊




best 풀이

function solution(s) {
    const arr = s.split(' ');

    return Math.min(...arr)+' '+Math.max(...arr);
}

sort 정렬대신 Math.min, Math.max를 사용했다.
효율적인 측면에서는 그래도 내 코드가 n이면 이건 2n이니 난 내 코드가 더 좋다고 본다..!!

function solution(s) {
    return s.split(' ').sort((a, b) => a - b)[0] + ' ' + s.split(' ').sort((a, b) => a - b)[s.split(' ').length - 1];
}

워후… 한줄이긴 한데 너무 불필요하게 메소드들을 반복사용한다. (내 코드 짱…!)


58. 숫자의 표현 🤔

programmers 

function solution(n) {
  let answer = 0;
  for (let i =0; i<=n; i++){
    if (n%i === 0 &&& i % 2 === 1) answer++
  }
  return answer;
}

모르겠어서 다른 분의 풀이를 참고하였다.ㅠ

주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수와 주어진 수의 홀수의 약수 갯수는 같다

라는 공식을 활용한 풀이법이다.

  • 15의 약수는 1, 3, 5, 15 이고, 이중 홀수는 4개이다.
  • 약수 1 : 연속하는 1개의 자연수의 합으로 표현 가능 > 15 = 15
  • 약수 3 : 연속하는 3개의 자연수의 합으로 표현 가능, 15를 3으로 나눈 값인 5로 표현할 수 있다. > 5 + 5 + 5 = 15 => 3 + 4 + 5 = 15
  • 약수 5 : 연속하는 5개의 자연수의 합으로 표현 가능, 15를 5로 나눈 값인 3으로 표현할 수 있다. > 3 + 3 + 3 + 3 + 3 => 1 + 2 + 3 + 4 + 5 = 15
  • 약수 15 : 연속하는 15개의 자연수의 합으로 표현 가능 > 모든 홀수(2n+1)는 n과 n+1로 표현 가능 > 7 + 8 = 15


function solution(n) {
  let answer = 0;
  for (let i = 1; i <= n; i++) {
    let total = 0;
    for (let j = i; j <= n; j++) {
      if (total === n) answer++;
      if (total > n) break;
      total += j;
    }
  }
  return answer;
}

이 코드는 위에 코드보다 성능은 현저히 떨어지지만 수학적 공식 없이 문제 본질만을 생각해서 쓸 수 있는 코드이다.
이 코드까지는 어떻게 짜겠는데 정말 저런 위의 코드같은 건 내가 할 수 있을까….싶다.😭
코테 하면서 알게 되는 수학의 중요성….😭😭



59. 다음 큰 숫자

programmers 

function solution(n) {
  let cnt = n
    .toString(2)
    .split("")
    .filter((i) => i === "1").length;
  while (n++) {
    if (
      n
        .toString(2)
        .split("")
        .filter((i) => i === "1").length === cnt
    )
      return n;
  }
}

처음에 문제보고 살짝 쫄았는데 잘했어…!!
대견하다..!!




best 풀이

function nextBigNumber(n) {
    var size = n.toString(2).match(/1/g).length
    while(n++) {
        if(size === n.toString(2).match(/1/g).length) return n
    }
}

1의 갯수를 세는 걸 정규식으로 해결했다. split()과 filter()를 거치던 내 코드보다 훨씬 좋다…
앞으로는 문자열에서 특정 문자를 찾을 때는 정규식을 활용하자.