3011. Find if Array Can Be Sorted

3011. Find if Array Can Be Sorted
Solved
Medium
Topics
Companies
Hint
You are given a 0-indexed array of positive integers nums.

In one operation, you can swap any two adjacent elements if they have the same number of 
set bits
. You are allowed to do this operation any number of times (including zero).

Return true if you can sort the array, else return false.

---

접근

주어진 숫자의 bit 표현에서 '1' 갯수가 동일한 숫자들은 swap 을 수행할 수 있습니다.

오름차순으로 정렬하기 위해서는 인접한 숫자들과 swap 이 필요한데 위 조건을 달성하지 못하여 swap 이 실패하는 경우는 오름차순 정렬을 수행할 수 없습니다.

 

인접한 숫자들과의 크기 비교로 정렬하는 방법인 'bubble sort' 를 참고하여, 정렬 규칙을 수립하고 swap 이 실패하는 지 확인합니다.

 

먼저, 주어진 숫자들의 'set bits' 를 얻기 위해 미리 계산하여 dict 에 정리합니다.

이후 정렬을 수행하며 'swap' 이 실패하는 경우를 찾습니다.

---

코드

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canSortArray = function(nums) {
  var bits = {};
  function getBits(v) {
      var i = 0;
      while(v > 0){
          if (v % 2 == 1) {
              i++;
          }
          v = v >> 1;
      }
      return i;
  }

  var count = nums.length;

  for (var i = 0; i < count; i++) {
      bits[nums[i]] = getBits(nums[i]);
  }

  function check(a, b) {
      return bits[a] == bits[b];
  }
  
  for(var i = 1; i < count; i++) {
      for(var j = 0; j < count - i; j++) {
          if (nums[j] > nums[j + 1]) {
              // swap
              if (!check(nums[j], nums[j + 1])) {
                  return false;
              }

              [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
          }
      }
  }

  return true;
};