[Level 0] 정수 반복 계산

문제

문자열 S 는 이진수로 표현된 양의 정수이다.

해당 정수에 대해서 아래의 연산을 수행한다.
- 만약 숫자가 짝수인 경우 해당 값을 2로 나눈다.
- 만약 숫자가 홀수인 경우 1을 뺀다.

연산의 결과가 0이 될 때까지 위 동작을 반복해서 수행했을 때, 수행된 연산의 횟수를 구하는 프로그램을 구현하라.

 

입력 형식

• 이진수로 이루어진 문자열 S

 

출력 형식

• 결과가 0이 될 때까지 필요한 연산 횟수를 정수로 반환

 

제약 사항

• 0 < S.length <= 100

 

입출력 예시

• 입력 : S = "1101"

• 출력 : 6
• 설명 : 1101은 십진수로 13이며, 아래와 같은 순서로 6번 동작한 후에 종료된다.
  13 → 12 → 6 → 3 → 2 → 1 → 0

 

---

내 풀이

function solution(S) {
    const num = parseInt(S,2);
    return operation(num,0);
}
function operation(n, count){
    if (n === 0) return count;

    if(n % 2 === 0) {
        return operation(n/2, ++count);
    }else{ 
        return operation(n-1, ++count);
    }
}

 

• 시간 복잡도 : O(log n)
• 설명 : 입력 값인 n이 2로 나눠질 때마다 절반으로 줄어든다. 이진수로 표현된 n을 계속해서 절반으로 나누면서 재귀적으로 함수를 호출하므로 시간 복잡도는 O(log n)이다.
  이 코드는 이진수로 표현된 n을 2로 나누거나 1을 빼는 작업을 반복하면서 0이 될 때까지의 연산 횟수를 구하는 함수이다. 따라서 입력 값 n의 이진수 표현에서 1의 개수를 세는 것과 동일한 기능을 수행한다. 이 코드는 주어진 이진수를 2로 나누거나 1을 빼는 작업을 반복하면서 이진수의 1의 개수를 구하므로 효율적인 방법이다. 입력 값 n이 매우 크더라도 이진수의 길이에 따라 연산 횟수가 크게 줄어들어 효율적인 알고리즘이다.

 

---