[2024] day 151. leetcode 1404. Number of Steps to Reduce a Number in Binary Representation to One

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 5월 29일 (수)
Leetcode daily problem

1404. Number of Steps to Reduce a Number in Binary Representation to One

https://leetcode.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/?envType=daily-question&envId=2024-05-29

Problem

문자열 s로 정수의 이진 표현이 주어지면 다음 규칙에 따라 정수를 1로 줄이는 단계 수를 반환한다.

-현재 숫자가 짝수이면 2로 나눈다

• 현재 숫자가 홀수이면 1을 더한다.

모든 테스트 사례는 항상 1에 도달할 수 있다는 것이 보장된다.

Solution

greedy

문제를 보면, 본질적으로 각 단계에서 오른쪽 끝의 비트를 제거하는 작업을 수행하고 있다. 숫자가 짝수일 경우 오른쪽 끝의 비트를 직접 제거하고 ,홀수 일 때는 1을 더해 짝수로 만든 후 비트를 제거한다.
따라서, 숫자가 짝수일 경우에는 비트를 제거하는데 한 단계가 더 필요하고 홀수 일 때는 두 단계가 필요하다.

주어진 숫자를 1로 만드는 작업은 이진 문자열의 오른쪽 끝에서부터 시작해서 가장 왼쪽의 1비트까지 모든 비트를 제거하는 것과 동일하다.
가장 왼쪽의 1비트는 항상 1이므로 제거하지 않고, 따라서 문자열을 오른쪽 끝부터 왼쪽 끝까지 순회하면서 각 비트가 1인지 0인지 확인한다. 1이면 두 단계를 더하고 비트가 0이면 한 단계를 더한다.

여기서 현재 비트가 1일 때 1을 더해 0을 만들고 2로 나누어 비트를 제거하면 새로운 비트가 발생할 수도 있는데, 이 추가 비트는 다른 변수에 넣어 값을 업데이트하며, 다음 비트의 홀수/짝수 여부를 확인할 때 추가 비트를 고려해야 한다.

현재 비트가 홀수면 추가 비트를 1로 설정하여 다음 비트에 반영한다.
왼쪽 끝 비트에 도달했을 때 추가 비트가 1이라면 이 추가 비트를 더하고 마지막 0을 제거하는 한 단계를 추가해야한다.

Code

class Solution:
    def numSteps(self, s: str) -> int:
        n = len(s)
        ans, add_bit = 0, 0
        
        for i in range(n-1, 0, -1):
            digit = int(s[i]) + add_bit
            
            if digit %2==1:
                ans +=2
                add_bit =1
                
            else:
                ans +=1
                
        return ans + add_bit

Complexicity

시간 복잡도

주어진 이진 표현의 문자열 s 의 길이만큼 탐색하므로 시간 복잡도는 O(n)이다.

공간 복잡도

상수 변수만 사용하므로 공간 복잡도는 O(1) 이다.