Leetcode 2948. Make Lexicographically Smallest Array by Swapping Elements

문제

You are given a 0-indexed array of positive integers nums and a positive integer limit.

In one operation, you can choose any two indices i and j and swap nums[i] and nums[j] if |nums[i] - nums[j]| <= limit.

Return the lexicographically smallest array that can be obtained by performing the operation any number of times.

An array a is lexicographically smaller than an array b if in the first position where a and b differ, array a has an element that is less than the corresponding element in b. For example, the array [2,10,3] is lexicographically smaller than the array [10,2,3] because they differ at index 0 and 2 < 10.

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

하나의 연산에서, 두 인덱스 i와 j를 선택하여 다음 조건을 만족하는 경우 nums[i]와 nums[j]를 교환할 수 있습니다:

• 두 숫자의 차이 ( \lvert nums[i] - nums[j] \rvert )가 limit 이하인 경우에만 교환이 가능합니다.

연산을 원하는 만큼 수행하여 얻을 수 있는 사전순으로 가장 작은 배열을 반환하세요.

사전순 비교 예시

배열 a	배열 b	비교 결과
[2,10,3]	[10,2,3]	배열 a가 b보다 사전순으로 작음 (인덱스 0에서 2 < 10)
[5,1,4]	[5,1,5]	배열 a가 b보다 사전순으로 작음 (인덱스 2에서 4 < 5)

배열 a가 배열 b보다 사전순으로 작다는 것은, 배열 a와 b가 처음으로 다른 위치에서, a의 해당 요소가 b의 해당 요소보다 작을 때를 의미합니다.

---

예시

nums = [1,5,3,9,8], limit = 2

• [1, 3, 5, 8, 9] 가 된다.

---

제한

• $1 <= nums.length <= 10^5$
• $1 <= nums[i] <= 10^9$
• $1 <= limit <= 10^9$

---

풀이법

• 이 문제는 생각 자체는 쉽지만 구현 과정이 조금 복잡하다고 생각해, 코드를 먼저 보고 풀이를 해보겠다.

class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        N = len(nums)

        target = [(v, i) for i, v in enumerate(nums)]

        target.sort()

        groups = [[]]

        for num, index in target:
            if len(groups[-1]) == 0 or num - groups[-1][-1][0] <= limit:
                groups[-1].append([num, index])
            else:
                groups.append([[num, index]])

        for group in groups:
            indices = [i for _, i in group]
            indices.sort()
            for i in range(len(group)):
                group[i][1] = indices[i]
        
        ans = [0] * N

        for group in groups:
            for v, i in group:
                ans[i] = v

        return ans

1. 그룹 만들기

• 차이가 limit 이하인 숫자들의 그룹을 만들어야 한다.
• 이를 위해 숫자를 미리 정렬하고, 이를 이용한다.
• 다만 나중에 숫자를 재정렬해야 하기 때문에 원래 있던 인덱스를 보존해야 한다.

        groups = [[]]

        for num, index in target:
            if len(groups[-1]) == 0 or num - groups[-1][-1][0] <= limit:
                groups[-1].append([num, index])
            else:
                groups.append([[num, index]])

2. 그룹 내부 정렬

• 만들어진 그룹이 의미하는것은 다음과 같다
  • 그룹 내에 있는 숫자들끼리는 마음대로 위치를 변경할수 있다.
  • 즉, 이 그룹 내부에서는 정렬이 가능하다는 의미이다.
  • 그렇기에, 받아온 인덱스를 내부적으로 정렬한다.
  • 이후 정렬된 인덱스로 그룹 내부의 인덱스를 정리한다.

        for group in groups:
            indices = [i for _, i in group]
            indices.sort()
            for i in range(len(group)):
                group[i][1] = indices[i]

3. 정답 생성

• 다시 그룹을 전부 순회하여 해당 index에 해당하는 값으로 정답 배열을 채운다.

        ans = [0] * N

        for group in groups:
            for v, i in group:
                ans[i] = v

        return ans

---

혹은?

class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        group = [deque()]

        m = {}

        target = [(v, i) for i, v in enumerate(nums)]

        target.sort()

        group_index = 0

        for v, i in target:
            if len(group[-1]) == 0 or v - group[-1][-1] <= limit:
                group[-1].append(v)
            else:
                group.append(deque([v]))
                group_index += 1
            m[i] = group_index

        ans = []

        for i in range(len(nums)):
            ans.append(group[m[i]].popleft())

        return ans

• 그룹을 만들때 해당 index가 어떤 그룹에 해당하는지를 작성해 두어 바로 꺼낼수도 있다.