[Leetcode]2191. Sort the Jumbled Numbers

1. 문제 :

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.
 

Example 1:

Input: mapping = [8,9,4,0,2,1,3,5,7,6], nums = [991,338,38]
Output: [338,38,991]
Explanation: 
Map the number 991 as follows:
1. mapping[9] = 6, so all occurrences of the digit 9 will become 6.
2. mapping[1] = 9, so all occurrences of the digit 1 will become 9.
Therefore, the mapped value of 991 is 669.
338 maps to 007, or 7 after removing the leading zeros.
38 maps to 07, which is also 7 after removing leading zeros.
Since 338 and 38 share the same mapped value, they should remain in the same relative order, so 338 comes before 38.
Thus, the sorted array is [338,38,991].
Example 2:

Input: mapping = [0,1,2,3,4,5,6,7,8,9], nums = [789,456,123]
Output: [123,456,789]
Explanation: 789 maps to 789, 456 maps to 456, and 123 maps to 123. Thus, the sorted array is [123,456,789].
 

Constraints:

mapping.length == 10
0 <= mapping[i] <= 9
All the values of mapping[i] are unique.
1 <= nums.length <= 3 * 104
0 <= nums[i] < 109

 

2. 풀이 : 

내가 풀었던 풀이 :

class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
        my_dict = {}
        duplicate = []
        for num in nums:
            word = ""
            for ele in str(num):
                word += str(mapping[int(ele)]) 
            if num in my_dict:
                duplicate.append(num)
                continue
            my_dict[num] = int(word) 
        nums = [key for key,value in sorted(my_dict.items(),key= lambda items: items[1])]
        for dup in duplicate:
            nums.insert(nums.index(dup),dup)
        return nums

내가 풀었던 풀이다. 딕셔너리를 만들어, 각 고유의 값을 키로, 그에 대응하는 value를 value로 두려고 했다. 하지만, 주어진 nums에는 중복된 수가 존재할 수 있었다. 이러면, dictionary는 사실 trash다. 하지만, 이왕 코드를 이렇게 짜놓은 거, 끝까지 작성해 보자 했다. 그렇다면 duplicate가 있을 때는 어떻게 처리할 것인가? duplicate list를 만들어서, dictionary에 key값이 존재한다면 추가를 하고, 나중에 nums.index(dup)를 실행해서, 해당하는 인덱스를 찾고, 거기에다가 삽입하는 방법을 이요했다. 사실, 코드를 적으면서도 너무 shitt 한 코드라고 판단했다. 앞으로 이런 코드를 버릴 수 있도록 새로운 방법을 많이 도입해야겠다. 

 

3. 풀이 : 

class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
        def convert(x):
            if x == 0 :
                return mapping[0] 
            z = 0
            pow = 1  
            while x > 0:
                q,r = divmod(x,10)
                z += mapping[r] * pow 
                x = q 
                pow *= 10 
            return z 
        n = len(nums)
        mapNum = [] 
        for i,num in enumerate(nums):
            mapNum.append([convert(num),i,num]) 
        mapNum.sort()
        for i in range(n):
            nums[i] = mapNum[i][2]
        
        return nums

 

이 code는 solution에서 그대로 가져왔다. 이 사람은 convert라는 함수를 이용해 value를 형성했다. 이 과정에서 1의 자리와 10의 자리를 구분하는 방법이 색달랐다. pow = 1일때는 1의 자리를 계산하고, pow = 10일때는 10의 자리를 계산할 수 있었다. 또한, convert mehtod에서 사용된 divmod(분자,분모)이 방법은 처음알았다. 이 divmod를 실행하면, 몫과 나머지가 한번에 나온다. 기존에 사용하던 //, %를 한번에 연산하는 것이다. 앞으로 자주 써먹어야겠다. 

 

이렇게 만들어진 , value값을 나는 dictionary에 저장했었지만, 이사람은 [convert(x), i, num]와 같이 리스트 안에 3개의 원소를 같이 저장했다. 그 후, sort를 이용하여 , 정렬했다. sort와 sorted의 차이점은 그동안 무시하고 있었는데 이번기회에 알게 되었다. sort는 원본 리스트를 변경시키는 메서드이고, sorted는 원본 리스트는 변경시키지 않고, 새로운 리스트를 생성한다. 따라서, mapNum.sort()는 mapNum이라는 원본 리스트를 sort 시킨다. 여기서 [convert(x), i, num]에서 i값을 추가한 이유는 convert(x) 값이 같을 경우, 원래의 nums 리스트 안에 있는 원소 순서를 따라야 하기 때문에, nums의 index값을 추가하여 , 값이 같을 때, nums의 index 순으로 정렬하게 하는 역할이다.