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

2025. 1. 25. 15:17·알고리즘/LeetCode

 

난이도: 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

하루 한 문제 챌린지. Contribute to laewonJeong/algorithmPractice development by creating an account on GitHub.

github.com

 

'알고리즘 > LeetCode' 카테고리의 다른 글

[LeetCode] 2658. Maximum Number of Fish in a Grid (Python)  (0) 2025.01.28
[LeetCode] 1462. Course Schedule IV (Python)  (0) 2025.01.27
[LeetCode] 802. Find Eventual Safe States (Python)  (0) 2025.01.24
[LeetCode] 1267. Count Servers that Communicate (Python)  (0) 2025.01.23
[LeetCode] 1765. Map of Highest Peak (Python)  (0) 2025.01.22
'알고리즘/LeetCode' 카테고리의 다른 글
  • [LeetCode] 2658. Maximum Number of Fish in a Grid (Python)
  • [LeetCode] 1462. Course Schedule IV (Python)
  • [LeetCode] 802. Find Eventual Safe States (Python)
  • [LeetCode] 1267. Count Servers that Communicate (Python)
Laewon Jeong
Laewon Jeong
  • Laewon Jeong
    래원
    Laewon Jeong
    글쓰기 | 관리
  • GitHub

    • github.com/laewonJeong
  • 전체
    오늘
    어제
    • 분류 전체보기 (172)
      • Docker 및 Kubernetes (11)
        • Docker (5)
        • Kubernetes (6)
      • Data Engineering (18)
        • Hadoop (5)
        • Spark (5)
        • Kafka (5)
        • Airflow (3)
      • CI|CD (3)
      • 알고리즘 (136)
        • 알고리즘 (2)
        • LeetCode (118)
        • 프로그래머스 (11)
        • BOJ (1)
        • 코딩테스트 대비 (4)
      • 서버 (2)
        • 미니 서버 (2)
      • 잡담 (1)
  • 태그

    BFS
    그래프
    백트래킹
    리트코드
    쿠버네티스
    programmers
    아파치 하둡
    docker
    분산
    Kubernetes
    누적합
    아파치 스파크
    티스토리챌린지
    DP
    우선순위큐
    Python
    오블완
    String
    dfs
    알고리즘
    Apache Spark
    leetcode
    도커
    코딩테스트
    이진탐색
    파이썬
    문자열
    분산처리
    프로그래머스
    heapq
  • 인기 글

  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
Laewon Jeong
[LeetCode] 2948. Make Lexicographically Smallest Array by Swapping Elements (Python)
상단으로

티스토리툴바