[LeetCode] 3011. Find if Array Can Be Sorted

https://leetcode.com/problems/find-if-array-can-be-sorted/?envType=daily-question&envId=2024-11-06

leetcode - Find if Array Can Be Sorted

문제 유형: 정렬, 비트마스킹, 슬라이딩 윈도우

문제 난이도: Medium

 

문제

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.

 

자연수 배열 nums가 주어진다.

한 번의 연산에, 당신은 이진 표현에서 1의 개수가 같은 두 인접한 요소를 스왑할 수 있다.

이를 0번 이상 할 수 있다.

이 규칙으로 배열을 정렬할 수 있다면 true, 아니면 false를 반환하시오.

 

풀이

left와 right를 만든다. 둘다 0부터 시작한다.

  right가 left와의 이진 표현의 수를 비교하고, 같다면 계속 밀어서 진행한다.

  left부터 right이전까지 정렬하고, left를 right로 복사한다.

이를 right가 n보다 작을 때까지 반복한다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops")
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    bool canSortArray(vector<int>& nums) {
        int n = nums.size();
        int left = 0, right = 0;
        while(right < n) {
            int leftPopCounts = __builtin_popcount(nums[left]);
            while(right < n && leftPopCounts == __builtin_popcount(nums[right])) right++;
            sort(nums.begin() + left, nums.begin() + right);
            left = right;
        }

        for(int i = 1; i < n; ++i) {
            if(nums[i] < nums[i-1]) return false;
        }
        return true;
    }
};