소프트웨어에 대한 모든 것

LeetCode 풀기 - 1342. Number of Steps to Reduce a Number to Zero 본문

알고리즘/LeetCode

LeetCode 풀기 - 1342. Number of Steps to Reduce a Number to Zero

앤테바 2021. 11. 7. 18:48
반응형

1342. Number of Steps to Reduce a Number to Zero

https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/

 

Number of Steps to Reduce a Number to Zero - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

문제)

솔루션1)

모듈레이션 연산을 수행해서 나머지가 0이면 even, 아니면 odd

even이면 나누기 2 연산, 아니면 -1 연산 후 카운팅을 증가.

num이 0이 될 때까지 반복연산

class Solution:
    def numberOfSteps(self, num: int) -> int:
        count = 0
        while num > 0:
            if num % 2 == 0:
                # even
                num /= 2                
            else:
                num -= 1
            count += 1
        return count

솔루션2)

비트 연산자, 비트 쉬프트 연산자를 활용해서 문제를 푼다.

우 비트 쉬프트 연산은 나누기 2 연산을 의미한다.

num의 이진수의 첫번째 자리가 1은 even을 의미한다.

class Solution:
    def numberOfSteps(self, num: int) -> int:
        ret = 0
        while num > 0:
            ret += 1 + (num & 1)
            num >>= 1
        return ret

솔루션3)

bin() 함수를 이용해서 10진수 num을 이진수 문자열로 변환한다.

앞으 '0b'는 제거한다.

이진수 문자열의 개 수 n번은 n번 나누기를 수행하면 0이 된다는 의미이다.

이진수 문자열에서 1의 개 수는 홀 수가 몇 번 나오는가를 의미한다. 

위 둘을 더하고 마이너스 1을 구하면된다. -1은 최상위 1이 두번 카운팅되기 때문에 -1을 취한다.

class Solution:
    def numberOfSteps(self, num: int) -> int:
        # without '0b'
        bin_str = bin(num)[2:]
        return len(bin_str) + bin_str.count('1') - 1

 

반응형
Comments