1로 만들기

문제설명

정수가 있을 때, 짝수라면 반으로 나누고, 홀수라면 1을 뺀 뒤 반으로 나누면, 마지막엔 1이 됩니다. 예를 들어 10이 있다면 다음과 같은 과정으로 1이 됩니다.

• 10 / 2 = 5
• (5 - 1) / 2 = 4
• 4 / 2 = 2
• 2 / 2 = 1

위와 같이 4번의 나누기 연산으로 1이 되었습니다.

정수들이 담긴 리스트 num_list가 주어질 때, num_list의 모든 원소를 1로 만들기 위해서 필요한 나누기 연산의 횟수를 return하도록 solution 함수를 완성해주세요.

입출력 예

num_list	result
[12, 4, 15, 1, 14]	11

입출력 예 설명

입출력 예 #1

12는 3번, 4는 2번, 15는 3번, 1은 0번, 14는 3번의 연산이 필요하기 때문에 총 11번의 연산이 필요합니다.

풀이

풀이 1.

function solution(num_list) {
  let count = 0;
  
  for (let num of list) {
    while (num > 1) {
      if (num % 2 === 0) {
        num /= 2;
      } else {
        num = (num - 1) / 2;
      }
      count++;
    }
  }
  
  return count;
}

풀이 2.

function solution(num_list) {
    return num_list
        .map(num => {
            const binary = num.toString(2);
            return binary.length - 1;
        })
        .reduce((a, c) => a + c);
}

풀이해설

function solution(num_list) {
    return num_list
  		// 각 숫자를 이진수로 변환하고, 연산 횟수를 곗한
        .map(num => {
      		// 숫자를 2진수로 변환
            const binary = num.toString(2);
      		// 2진수의 길이에서 1을 뺀 것이 연산 횟수
      		// 예: 12 (이진수: '1100') -> 길이 4 -> 연산 횟수는 3
            return binary.length - 1;
        })
  		// 모든 숫자의 연산 횟수를 합산
        .reduce((a, c) => a + c);
}

이진수

const binary = num.toString(2);

return binary.length - 1;

이진수에서 각 자리는 오른쪽에서 왼쪽으로 2의 거듭제곱을 나타내며, 1100는 2^3, 2^2, 0, 0으로 12(= 8 + 4)이다.

1. 1100(12)을 2로 나누는 것은 마지막 '0'을 제거하는 것과 같다.

   • 110(6)

2. 110(6)에서 다시 2로 나누는 것도 마지막 '0'을 제거하는 것과 같다.

   • 11(3)

3. 11(3)은 홀수이므로 먼저 1을 빼고(10, 즉 2), 그 다음 2로 나눈다.

   • 1(1)

이 과정에서 총 세 번의 연산이 수행된다. 이는 이진수 1100의 길이 4에서 1을 뺀 값과 일치한다.

이 방식으로 숫자를 이진수로 변환한 뒤, 그 길이에서 1을 빼는 것으로 필요한 연산횟수를 계산할 수 있다.