문제

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.

요약

10진수의 정수 배열에 대해서 인접한 두 수가 2진법으로 표현시 1의 개수가 같으면 둘의 자리를 교환할 수 있다.

이때 이 배열을 정렬할 수 있는가?

풀이

새로운 배열에 인접하면서 2진법 표현시 1의 개수가 같을경우 최대, 최소를 저장하며 2진법 표현이 바뀔 경우 이전 2 배열의 최대 최소를 비교한다 (만약 선행 배열의 최대가 후행의 최소보다 클경우 정렬이 불가능하다)

코드

class Solution {
    public boolean canSortArray(int[] nums) {
        int[] arr = new int[nums.length];
        int pre = count(nums[0]);
        int root = 0;
        arr[0] = nums[0];

        for (int i = 1; i < nums.length; i ++) {
            int c = count(nums[i]);
            if (c != pre) {
                if (root != 0 && arr[root-1] > arr[root]) {
                    return false;
                }
                pre = c;
                root = i;
                arr[i] = nums[i];
                continue;
            }
            arr[i] = Math.max(arr[i-1], nums[i]);
            arr[root] = Math.min(arr[root], nums[i]);
        }
        if (root != 0 && arr[root-1] > arr[root]) {
            return false;
        }
        return true;
    }

    private int count(int num) {
        int count = 0;
        while (num > 0) {
            count += num %2;
            num/=2;
        }
        return count;
    }
}

풀이 시간

1시간 20분 (인접함을 못봐서 해맴)

체감 난이도

중간정도?