[LeetCode] 1356 - Sort Integers by The Number of 1 Bits

문제

• 링크: https://leetcode.com/problems/sort-integers-by-the-number-of-1-bits
• 난이도: Easy
• 태그: 배열, 비트 조작, 정렬
• 결과: Time: 0 ms (100%), Space: 14.9 MB (26.68%)

풀이

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        vector<pair<int, int>> pv;
        for(int i = 0; i < arr.size(); ++i) {
            pv.emplace_back(count1Bit(arr[i]), arr[i]);
        }

        sort(pv.begin(), pv.end());

        vector<int> res;
        res.reserve(arr.size());
        for(int i = 0; i < arr.size(); ++i) {
            res.push_back(pv[i].second);
        }

        return res;
    }

private:
    int count1Bit(int num) {
        int cnt = 0;
        while (num != 0)
        {
            if(num % 2 == 1)
            {
                cnt++;
            }
            num /= 2;
        }

        return cnt;
    }
};

오늘의 Daily Question. 나는 이렇게 풀었다. LeetCode는 Runtime별로 코드 샘플을 볼 수 있는데, 0ms 코드 샘플이 아래와 같았다.

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(),arr.end() , [] (int a, int b){
        int countA=__builtin_popcount(a);
        int countB=__builtin_popcount(b);
        if(countA==countB) return a<b;
        return countA<countB;
        });
        return arr;
    }
};

… __builtin_popcount라는게 있었어?? 게다가 reference로 넘어온 배열을 건들고 있어??? 이 자식들, 아주 간편한 세상에서 살고 있었구나.

먼저, __builtin_popcount는 set된 비트의 개수를 세어주는 함수이다(아마 gcc intrinsic인 듯). 그리고 참조로 넘긴 배열은 건드리지 말라는 의도로 이해하고 코드를 짰는데, 그런거 없었다. 앞으로는 조금 더 편하게(?) 코드를 짜도 될 것 같다.

그리고 그때그때 비트 개수를 세도 0ms가 나올 정도로 빠르구나. ‘매번 비트 개수를 셀 수는 없으니 pair로 묶어야겠지?’라는 생각이었는데 말이다.

LeetCode는 이렇게 다른 사람들의 코드를 볼 수 있는 점이 좋은 것 같다. 따로 검색해볼 필요 없이 사이트에서 지원하니 편하다.

배운 점과 후기

LeetCode에는 Bit Manipulation 문제가 많다고 들었는데, __builtin_popcount를 눈에 익혀두는게 좋을 것 같다.