(C++) - LeetCode (easy) 338. Counting Bits

https://leetcode.com/problems/counting-bits/description/

Counting Bits - LeetCode

이진수 변환 구현 문제였습니다.

📕 풀이방법

📔 풀이과정

0 ~ n까지 for loop를 수행합니다.

1. 매 loop별 수를 이진수로 변환된 문자열로 변환하는 함수 getBitString을 수행합니다.

bit 수만 세면 되므로 reverse를 하지 않은 채로 반환해줍니다.

2. 변환한 문자열에 대해 for loop를 수행하며 1bit를 세줘 cnt에 저장합니다.

3. vector ans에 cnt를 저장합니다.

* 이진수로 2로 나누며 변환하는데 logn. 해당 동작을 n만큼 수행하므로 O(nlogn) 시간 복잡도를 가집니다.

---

📕 Code

📔 C++

class Solution {
public:
    string getBitString(int num) {
        string bitString;
        while(num) {
            bitString += to_string(num%2);
            num /= 2;
        }
        return bitString;
    }
    vector<int> countBits(int n) {
        vector <int> ans;
        for(int i = 0; i <= n; i++) {
            string bitString = getBitString(i);
            int cnt = 0;
            for(auto b : bitString) {
                if(b == '1') cnt++;
            }
            ans.push_back(cnt);
        }
        return ans;
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.