[LeetCode] 2948. Make Lexicographically Smallest Array by Swapping Elements (Python)

 

난이도: Medium

문제 설명

---

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.

 

문제 설명

---

Example 1:

Input: nums = [1,5,3,9,8], limit = 2
Output: [1,3,5,8,9]
Explanation: Apply the operation 2 times:
- Swap nums[1] with nums[2]. The array becomes [1,3,5,9,8]
- Swap nums[3] with nums[4]. The array becomes [1,3,5,8,9]
We cannot obtain a lexicographically smaller array by applying any more operations.
Note that it may be possible to get the same result by doing different operations.

Example 2:

Input: nums = [1,7,6,18,2,1], limit = 3
Output: [1,6,7,18,1,2]
Explanation: Apply the operation 3 times:
- Swap nums[1] with nums[2]. The array becomes [1,6,7,18,2,1]
- Swap nums[0] with nums[4]. The array becomes [2,6,7,18,1,1]
- Swap nums[0] with nums[5]. The array becomes [1,6,7,18,1,2]
We cannot obtain a lexicographically smaller array by applying any more operations.

Example 3:

Input: nums = [1,7,28,19,10], limit = 3
Output: [1,7,28,19,10]
Explanation: [1,7,28,19,10] is the lexicographically smallest array we can obtain because we cannot apply the operation on any two indices.

 

제한사항

---

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= limit <= 109

 

✏️ Solution(솔루션)

---

class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        n = len(nums)
        sort_nums = sorted([(num, i) for i, num in enumerate(nums)])
        groups, group_idxs = [], []
        now_group, now_group_idx = [sort_nums[0][0]], [sort_nums[0][1]]

        for i in range(1, n):
            if abs(sort_nums[i-1][0] - sort_nums[i][0]) <= limit:
                now_group.append(sort_nums[i][0])
                now_group_idx.append(sort_nums[i][1])
            else:
                groups.append(sorted(now_group))
                group_idxs.append(sorted(now_group_idx))
                now_group, now_group_idx = [sort_nums[i][0]], [sort_nums[i][1]]
        
        groups.append(sorted(now_group))
        group_idxs.append(sorted(now_group_idx))      

        for group, group_idx in zip(groups, group_idxs):
            for num, idx in zip(group, group_idx):
                nums[idx] = num
        
        return nums

 

어려운 문제였다..

 

문제를 계속봐도 어떻게 접근해야할지 떠오르지를 않아 Editorial에서 접근법만 읽어보고 풀었다.

 

Grouping이랑 Sorting을 통해서 이를 풀 수 있다는 것을 깨닫고 이를 코드로 구현했다.

 

아래 그림은 Editorial의 그림을 가져온 것이다.

https://leetcode.com/problems/make-lexicographically-smallest-array-by-swapping-elements/editorial

https://leetcode.com/problems/make-lexicographically-smallest-array-by-swapping-elements/editorial

 

사실 생각치도 못한 접근 방법이라서 당황했지만, 한편으로 모르던 것을 알게 되어 좋았던 것 같다.

이렇게 새로 알게된 방법을 내 것으로 만드는게 좋을 것 같다.

---

문제: 2948. Make Lexicographically Smallest Array by Swapping Elements

 

깃허브: github

algorithmPractice/LeetCode/3219-make-lexicographically-smallest-array-by-swapping-elements at main · laewonJeong/algorithmPract