Leetcode 3011 Find if Array Can Be Sorted (Java)

 

https://leetcode.com/problems/find-if-array-can-be-sorted

class Solution {

    static class Pair{
        int minV;
        int maxV;

        public Pair(int minV, int maxV){
            this.minV=minV;
            this.maxV=maxV;
        }

    }

    public boolean canSortArray(int[] nums) {
        
        int n=nums.length;

        int[] setbit=new int[n];
        
        for(int i=0;i<n;i++){

            int cur=nums[i];

            while(cur>0){
                if(cur%2==1){
                    setbit[i]++;
                }
                cur/=2;
            }

        }

        int minv=nums[0];
        int maxv=nums[0];
        int curset=setbit[0];

        List<Pair> pair=new ArrayList<>();

        for(int i=1;i<=n;i++){
            if(i==n || curset!=setbit[i]){
                pair.add(new Pair(minv, maxv));
                if(i!=n){
                    maxv=nums[i];
                    minv=nums[i];
                    curset=setbit[i];
                    continue;

                }
            }
            else{
                maxv=Math.max(maxv, nums[i]);
                minv=Math.min(minv, nums[i]);
            }
        }

        for(int i=0;i<pair.size()-1;i++){
            if(pair.get(i).maxV>pair.get(i+1).minV){
                return false;
            }
        }

        return true;

    }

}

1. 문제

100 이하 길이, 2^8 이하의 자연수가 담긴 nums 배열이 주어진다. 해당 배열을 정렬하려 하는데 배열 내 숫자에서 이진법으로 바꾸었을 때 1의 개수가 같은 수 끼리만 위치를 바꿀 수 있다. 이 때 해당 규칙을 지키며 배열을 정렬할 수 있다면 true, 없다면 false를 반환하라.

2. 풀이

예시를 하나 보도록 하자

해당 예시에서 8, 4, 2는 비트 1의 수가 1개, 30, 15는 4개로 서로 swap할 수 있다. 그러면 8, 4, 2를 정렬할 수 있고, 30, 15를 정렬할 수 있다. 앞의 배열에서 가장 큰 수보다 뒷 배열의 가장 작은 수가 더 크므로 해당 배열은 모두 정렬할 수 있게 된다.

 즉 전체 배열을 비트 1의 수가 같은 것 끼리 나눴을 때 앞 배열의 최댓값이 뒷 배열의 최솟값 이하여야 정렬이 가능하다.

        int n=nums.length;

        int[] setbit=new int[n];
        
        for(int i=0;i<n;i++){

            int cur=nums[i];

            while(cur>0){
                if(cur%2==1){
                    setbit[i]++;
                }
                cur/=2;
            }

        }

우선 배열의 각 수에 대해 비트 1의 개수를 구해 setbit라는 배열에 저장해주었다.

        static class Pair{
            int minV;
            int maxV;

            public Pair(int minV, int maxV){
                this.minV=minV;
                this.maxV=maxV;
            }

        }

        int minv=nums[0];
        int maxv=nums[0];
        int curset=setbit[0];

        List<Pair> pair=new ArrayList<>();

        for(int i=1;i<=n;i++){
            if(i==n || curset!=setbit[i]){
                pair.add(new Pair(minv, maxv));
                if(i!=n){
                    maxv=nums[i];
                    minv=nums[i];
                    curset=setbit[i];
                    continue;

                }
            }
            else{
                maxv=Math.max(maxv, nums[i]);
                minv=Math.min(minv, nums[i]);
            }
        }

각 서브배열의 최댓값과 최솟값을 넣기 위해 Pair 클래스를 생성, 이를 이용해 리스트를 만들었다. 반복문을 돌면서 이전의 비트 1의 개수와 같다면 최댓값, 최솟값을 갱신해주고, 그렇지 않다면 이전 배열의 최댓값, 최솟값을 리스트에 넣어준다. 그리고 다음 숫자와 비교하기 위해 curset를 현재 배열의 비트 개수로 초기화해준다.

        for(int i=0;i<pair.size()-1;i++){
            if(pair.get(i).maxV>pair.get(i+1).minV){
                return false;
            }
        }

        return true;

이제 리스트를 돌면서 현재의 최댓값보다 이후의 최솟값이 더 크다면 정렬이 불가능하므로 false를, 반복문을 통과했다면 true를 반환한다.