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

https://leetcode.com/problems/sort-integers-by-the-number-of-1-bits/description/

Sort Integers by The Number of 1 Bits - LeetCode

leetcode - Sort Integers by The Number of 1 Bits

문제 유형: 비트마스킹

문제 난이도: Easy

 

문제

You are given an integer array arr. Sort the integers in the array in ascending order by the number of 1's in their binary representation and in case of two or more integers have the same number of 1's you have to sort them in ascending order.

Return the array after sorting it.

 

정수 배열 arr이 주어집니다. 배열을 2진수의 1의 개수 기준 오름차순정렬 하고, 같은 개수인 경우는 숫자의 크기를 기준으로 오름차순정렬하시오.

 

풀이

배열을 2진수의 1의 개수 기준 오름차순정렬 하고, 같은 개수인 경우는 숫자의 크기를 기준으로 오름차순정렬해주면 된다.

 

코드

C++

class Solution {
public:
    static int bitcount(int n) {
        int count = 0;
        while(n > 0) {
            if(n % 2 == 1) count++;
            n /= 2;
        }
        return count;
    }

    static bool comp(int a, int b) {
        int countA = bitcount(a);
        int countB = bitcount(b);
        
        if(countA == countB) return a < b;
        else return countA < countB;
    }

    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), comp);
        return arr;
    }
};