[코테연습] 3011. Find if Array Can Be Sorted

비트 / 배열 / 정렬 문제

문제 분석

• 주어진 배열을 특정 조건에 따라 정렬할 수 있는지를 확인하는 문제입니다.
• 조건: 이진 표현에서 설정된 비트의 개수가 같은 경우에만 두 수를 교환할 수 있습니다.
• 목표: 주어진 조건을 만족하면서 배열을 오름차순으로 정렬 가능한지 판단하는 것입니다.

문제 풀이 (코드 순서대로 설명)

• 초기 정렬 상태 확인:
  • 배열이 이미 오름차순으로 정렬되어 있는지 검사합니다.
  • 만약 정렬되어 있다면 바로 true를 반환하여 추가적인 처리를 하지 않습니다.
• 비트 조건에 따른 반복적인 교환 시도:
  • 배열의 요소들을 반복적으로 순회하며 교환을 시도합니다.
  • while 루프를 통해 교환이 더 이상 발생하지 않을 때까지 정렬을 계속 시도합니다.
  • for 루프를 사용해 배열의 인접한 요소들을 비교합니다.
    • 각 요소 쌍에서 비트 개수가 동일하고 앞 요소가 뒤 요소보다 클 경우 교환을 수행합니다.
    • 교환이 발생할 때마다 changed를 true로 설정하여 다음 반복을 이어갑니다.
• 최종 정렬 상태 확인:
  • 모든 가능한 교환이 이루어진 후, 배열이 완전히 오름차순으로 정렬되었는지 확인합니다.
  • 최종적으로 정렬된 배열이라면 true, 그렇지 않다면 false를 반환합니다.

 

> java

 

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

        // 이미 정렬되어 있는지 확인
        if (isSorted(nums)) {
            return true;
        }

        // 정렬 가능한지 확인 (비트 조건에 따라 반복적으로 정렬 시도)
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i < n - 1; i++) {
                if (Integer.bitCount(nums[i]) == Integer.bitCount(nums[i + 1]) && nums[i] > nums[i + 1]) {
                    // 교환 가능하다면 교환
                    int temp = nums[i];
                    nums[i] = nums[i + 1];
                    nums[i + 1] = temp;
                    changed = true;  // 교환이 발생했음을 기록
                }
            }
        }

        // 배열이 정렬되었는지 확인
        return isSorted(nums);
    }

    // 정렬 여부를 확인하는 함수
    private boolean isSorted(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) {
                return false;
            }
        }
        return true;
    }
}

 

> python

 

class Solution:
    def canSortArray(self, nums: List[int]) -> bool:
        n = len(nums)
        # 이미 정렬되어 있는지 확인
        if nums == sorted(nums):
            return True

        changed = True
        while changed:
            changed = False
            for i in range(n - 1):
                if bin(nums[i]).count('1') == bin(nums[i + 1]).count('1') and nums[i] > nums[i + 1]:
                    nums[i], nums[i + 1] = nums[i + 1], nums[i]  # 파이썬의 간단한 스왑 방식
                    changed = True

        return nums == sorted(nums)