[Leetcode] 1404. Number of Steps to Reduce a Number in Binary Representation to One - Python, 구현

접근

1. 구현
2. 비트 조작

조건을 만족하며 시행 횟수를 구하는 문제이다. 반복문을 활용하여 최대한 효율적으로 풀어야 한다. 이진법 변환 + 비트 조작으로 풀이가 가능하나, 문자열 그대로 풀어보았다. 아래와 같이 계산한다.

• index 1까지 역순으로 for문 순회
• “1”이 등장하지 않으면 시행횟수 +1
• “1”이 등장하면 시행횟수 +2
• “1”이 등장한 이후부터는
  • 현재 char가 “1”이라면 +1
  • 현재 char가 “0”이라면 +2

풀이

class Solution:
    def numSteps(self, s: str) -> int:

        answer = temp = 0

        for i in range(len(s)-1, 0, -1):
            if s[i] == "1":
                if temp:
                    answer += 1
                else:
                    temp = 1
                    answer += 2
            else:
                if temp:
                    answer += 2
                else:
                    answer += 1
        
        if temp:
            answer += 1
        
        return answer