[leetcode] 3011. Find if Array Can Be Sorted

문제 설명 :

정수 array에서, 2진수로 표현했을 때 1의 개수가 같은 것끼리 교환 operation이 가능할 때, sorting상태로 만들 수 있는지 찾는 것.

방법 : 1의 개수를 count

• 2진수 1의 개수를 세기 위해 count 해줌
• 이후 bubble sort / 근데 어차피 인접한거 옮기는 과정에서 1의 개수가 다르면 False다.
  ㄴ 따라서 selection sort방식으로 간단히 구현 후 테스트하였음.

Code

class Solution:
    def sorting(self, nums, set_bits):
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] > nums[j]:
                    if set_bits[i] != set_bits[j]:
                        return False
                    nums[i], nums[j] = nums[j], nums[i]
        return True
    def canSortArray(self, nums: List[int]) -> bool:
        set_bits = []
        for num in nums:
            count = 0
            while num >= 1:
               if num%2==1:
                    count += 1
               num//=2
            set_bits.append(count)
        return self.sorting(nums, set_bits)

Selection sort로 구현했기 때문에, 항상 O(n^2)
ㄴ bubble sort로 구현한다면 worst case 는 O(n^2), best case는 O(n)