3011. Find if Array Can Be Sorted

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

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:10:48

 

---

 

문제 설명

 

 

양의 정수로 구성된 0-인덱스의 배열 nums가 주어진다.

 

하나의 연산에서, 두 인접한 숫자가 같은 set bit(이진수로 나타냈을 때 1의 개수)를 가질 때 교환할 수 있다. 0번을 포함해서 임의의 숫자대로 이 연산을 수해할 수 있다.

 

만약 배열을 정렬할 수 있다면 True를, 그렇지 않다면 False를 반환하라.

---

 

풀이

 

첫 번째 풀이.

nums의 길이가 100을 넘지 않으므로, 그냥 버블 정렬해보자. 정렬 과정에서 인접한 숫자들을 계속해서 참조하므로 확인이 가능하다. 만약 조건이 충족되지 않는다면(set bit가 같지 않으면) 정렬이 불가하므로 False를, 모든 정렬이 성공한다면 True를 반환하면 된다. 이 방식은 O(n^2)이 소요된다.

 

여기서 문제를 재해석하면, 좀 더 효율적인 풀이가 가능하다. set bit를 기준으로 접근해보자. 동일한 set bit여야지 인접한 두 수를 교환할 수 있다면, set bit 관점에서는 교환 전후로 위치가 변하지 않는다. 이말인즉슨, 같은 set bit구간에서만 정렬이 가능하다는 의미이다.

 

그럼 set bit 구간끼리 정렬을 수행해보자. 그 정렬 수행 결과가 전체 정렬 수행 결과와 같아야 정렬이 가능하다는 의미와 같다.

아니, 정렬을 수행할 필요도 없이, 구간의 최솟값과 최댓값을 알기만 하면 된다. 각 set bit 구간을 비교하며, 이전 구간의 최댓값이 이후 구간의 최솟값보다 큰지 비교해보자.

 

• 예를 들어 [2 .... 16], [15 .... 30] 구간이 있다고 가정하자.
  • 그렇다면 이전 구간의 최댓값 16보다 이후 구간의 최솟값 15가 작다는 사실을 알 수 있다.
  • 즉 전체 정렬에는 실패한 셈이다. False를 반환한다.
• 예를 들어 [2 .... 8], [15 .... 30] 구간이 있다고 가정하자.
  • 여기서는 이전 구간의 최댓값 8보다 이후 구간의 최솟값 15가 더 크다. 따라서 두 구간 간에서는 확실히 정렬이 성립한다.
  • 각 구간 내에서는 정렬이 가능하다. 
  • 따라서 전체 정렬 수행이 가능하다. True를 반환한다.

 

최댓값, 최솟값만을 저장하면 되므로 O(n)의 한 번의 순회 안에 정렬 성공 여부를 판단할 수 있겠다.

 

 

풀이 코드

class Solution:
    def canSortArray(self, nums: List[int]) -> bool:
        if len(nums) == 1 :
            return True
        res = [[nums[0], nums[0], bin(nums[0]).count('1')]]
        for i in range(1, len(nums)) :
            n = nums[i]
            tmp = bin(n).count('1')
            if tmp != res[-1][2] :
                res.append([n, n, tmp])
            else :
                res[-1][0] = min(res[-1][0], n)
                res[-1][1] = max(res[-1][1], n)
            if len(res) > 1 and res[-2][1] > res[-1][0] :
                return False
        return True

풀이 완료!