[LeetCode] 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
• 난이도: Medium
• 태그: 문자열, 비트 조작, 시뮬레이션
• 결과: Time: 0 ms (100%), Space: 8.8 MB (83.16%)

풀이

class Solution {
public:
    int numSteps(string s) {
        int n = s.size();
        int cnt = 0;
        bool carry = false;
        for (int i = n - 1; i > 0; --i) 
        {
            if (s[i] == '1')
            {
                if (carry)
                {                    
                    cnt++;
                }
                else
                {
                    carry = true;
                    cnt += 2;
                }
            }
            else
            {
                if (carry)
                {
                    cnt += 2;
                }
                else
                {
                    cnt++;
                }
            }
        }

        if (carry)
        {
            cnt++;
        }

        return cnt;
    }
};

오늘의 Daily Question. 문제 설명을 읽고 문자열 형태 그대로 간단하게 계산할 수 있을거라고 생각했고, 그대로 구현에 옮겼다.

또 다른 샘플 코드로는 아래와 같은 형태가 있었다.

class Solution {
public:
    int numSteps(string s) {
        int count = 0;

        while (s != "1") {
            if (s.back() == '0') {
                s.pop_back();
            } else {
                int i = s.size() - 1;

                while (i >= 0 && s[i] == '1') {
                    s[i] = '0';
                    i--;
                }

                if (i < 0) {
                    s = "1" + s;
                } else {
                    s[i] = '1';
                }
            }

            count++;
        }

        return count;
    }
};

이건 조금 더 시뮬레이션에 가까운 풀이인 것 같다. 이러나 저러나 상관 없지만, 나는 굳이 직접 해볼 필요 없이 순회하면서 계산하는게 간단한 것 같아서 그렇게 구현했다.

배운 점과 후기

어제자 문제가 Easy인걸 생각해보면 이것도 Easy로 분류되어야하지 싶다.