[LeetCode] 2191. Sort the Jumbled Numbers

https://leetcode.com/problems/sort-the-jumbled-numbers/description/

leetcode - Sort the Jumbled Numbers

문제 유형 : 정렬, 해시

문제 난이도 : Medium

 

문제

You are given a 0-indexed integer array mapping which represents the mapping rule of a shuffled decimal system. mapping[i] = j means digit i should be mapped to digit j in this system.

The mapped value of an integer is the new integer obtained by replacing each occurrence of digit i in the integer with mapping[i] for all 0 <= i <= 9.

You are also given another integer array nums. Return the array nums sorted in non-decreasing order based on the mapped values of its elements.

Notes:

• Elements with the same mapped values should appear in the same relative order as in the input.
• The elements of nums should only be sorted based on their mapped values and not be replaced by them.

 

0-indexed의 정수 배열 mapping이 있다. mapping[i] = j에서, i는 j로 매핑된다는 의미이다.

mapping은 길이가 10이다.

 

당신은 정수 배열 nums를 받는다. nums를 매핑된 값에 대해 비내림차순으로 정렬하여 반환하시오.

 

매핑된 값이 같다면, 기존 순서를 유지하세요.

매핑된 값으로 값이 대체되면 안됩니다.

 

풀이

해시맵<int, int>를 만들어서, 매핑된 숫자를 저장시킨다.

매핑된 숫자는 자릿수별로 잘라서 매핑시키고 더해서 숫자를 저장하면 된다.

 

그리고, 해시맵의 값을 기반으로 정렬해서 반환해주면 된다.

자세한 건 코드를 참조하면 되겠다.

 

코드

C++

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

class Solution {
public:
    int getMappedNum(vector<int>& mapping, int num) {
        if(num == 0) return mapping[0];

        int res = 0;
        int digit = 1;
        while(num > 0) {
            res += digit * mapping[num % 10];
            num /= 10;
            digit *= 10;
        }

        return res;
    }

    vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> mp;

        for(const auto &num : nums) {
            mp[num] = getMappedNum(mapping, num);
        }
        
        sort(nums.begin(), nums.end(), [&mp](const auto &a, const auto &b){
            return mp[a] < mp[b];
        });

        return nums;
    }
};