[2024] day 204. 2191. Sort the Jumbled Numbers

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 7월 24일 (수)
Leetcode daily problem

2191. Sort the Jumbled Numbers

https://leetcode.com/problems/sort-the-jumbled-numbers/?envType=daily-question&envId=2024-07-24

Problem

셔플된 10진 시스템의 매핑 규칙을 나타내는 0-index 정수 배열 mapping이 주어진다. mapping[i] = j는 이 시스템에서 숫자 i가 숫자 j에 매핑되어야 함을 의미합니다.

정수의 매핑된 값은 정수에서 숫자 i의 각 발생을 모두 0 <= i <= 9에 대해 mapping[i]로 대체하여 얻은 새로운 정수이다.

또 다른 정수 배열인 nums가 제공될 때, 해당 요소의 매핑된 값을 기반으로 내림차순으로 정렬된 배열 nums를 반환한다.

Notes:

• 동일한 매핑된 값을 가진 요소는 입력과 동일한 상대 순서로 나타나야 한다.
• nums의 요소는 매핑된 값을 기준으로만 정렬되어야 하고 해당 값으로 대체되어서는 안 된다.

Solution

주어진 숫자 배열을 특정 방식으로 변환하여 정렬하는 문제이다.
숫자 배열을 매핑하여 반환하는 함수를 만들어 sorted 함수를 사용해 정렬의 함수로 사용하여 반환한다.
(sorted 함수는 주어진 iterable(리스트, 튜플, 문자열 등)을 정렬된 새로운 리스트로 반환하고, 원래의 iterable은 변경되지 않는다. )

Code

class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
        
        def mapNum(num):
            transformed_nums = []
            for digit in str(num):
                transformed_nums.append(str(mapping[int(digit)]))
            transformed_num = ''.join(transformed_nums)
            return int(transformed_num)
        
        return sorted(nums, key=mapNum)

Complexicity

시간 복잡도

위의 mapNum 함수는 숫자를 문자열로 변환하고, 각 숫자를 mapping 배열로 매핑하여 새로운 숫자로 변환한다. 주어진 nums 배열의 원소들을 num이라고 할때 num의 자리수가 m이면 변환작업은 각 자리수 마다 상수 연산을 수행하므로 O(m)이다. 그리고 nums에 있는 모든 숫자에 대해 작업이 이뤄지므로 nums의 배열을 n이라고 한다면, O(m*n)이 소요된다.

매핑 작업이 끝난 후 sorted 내장 함수로 정렬할 때 O(nlogn)이 소요되는데, 여기서 키 함수 mapNum을 호출하면서 전체 시간 복잡도는 O(n*mlongn) 이다.

공간 복잡도

sorted 함수에서 정렬하기 위해 새로운 리스트를 생성하고, 반환된 정렬 리스트는 O(n)의 추가 공간을 사용한다.

즉, 전체 공간복잡도는 O(n) 이다.