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

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

leetcode - Make Lexicographically Smallest Array by Swapping Elements

문제 유형: 우선순위큐, 유니온-파인드

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

 

0-indexed의 양의정수 배열 nums와 정수 limit이 주ㄴ어진다.

한 번의 연산으로, 두 인덱스 i, j를 골라서 nums[i]와 nums[j]의 차가 limit이하라면 스왑할 수 있다.

이 연산을 적용해서 얻을 수 있는 사전순으로 가장 작은 배열을 구하시오.

사전순으로 작다는 의미는,  앞쪽의 같은 인덱스에서 더 작은 요소를 가진 것을 의미합니다.

 

풀이

 

최소 힙 우선순위 큐를 만들어서, {수의 값, 인덱스}로 넣는다.

우선순위 큐의 맨 위와 마지막 요소와의 차가 limit이하인 동안, 계속 뽑아서 배열에 인덱스와 수 따로 넣는다.

수는 이미 정렬되어있을 것이고, 인덱스 부분을 정렬해서 해당 인덱스들에 순차적으로 정렬된 수를 넣어주면 된다.

 

아니면, 유니온-파인드로 풀 수 있다. limit이라하면 같은 컴포넌트로 병합해놓고, 그 같은 집합들끼리 안에서 정렬하면 된다.

아래 코드는 우선순위 큐를 이용했다.

 

 

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
        int n = nums.size();
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

        for(int i = 0; i < n; ++i) {
            pq.push({nums[i], i});
        }

        while(!pq.empty()) {
            auto curr = pq.top();
            pq.pop();
            vector<int> indices;
            vector<int> subseq;
            indices.push_back(curr.second);
            subseq.push_back(curr.first);
            while(!pq.empty() && pq.top().first - curr.first <= limit) {
                curr = pq.top();
                pq.pop();
                indices.push_back(curr.second);
                subseq.push_back(curr.first);
            }

            sort(indices.begin(), indices.end());
            int m = indices.size();
            for(int i = 0; i < m; ++i) {
                nums[indices[i]] = subseq[i];
            }
        }

        return nums;
    }
};