[LeetCode] 1122. Relative Sort Array (Python)

 

난이도: Easy

 

문제 설명

---

Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1.

 

Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2. Elements that do not appear in arr2 should be placed at the end of arr1 in ascending order.

 

문제 예제

---

Example 1:

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]

Example 2:

Input: arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
Output: [22,28,8,6,17,44]

 

제한 사항

---

• 1 <= arr1.length, arr2.length <= 1000
• 0 <= arr1[i], arr2[i] <= 1000
• All the elements of arr2 are distinct.
• Each arr2[i] is in arr1.

 

✏️ Solution(솔루션)

---

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        arr = []
        n = len(arr2)

        arr2_with_idx = {k:v for v, k in enumerate(arr2)}

        for num in arr1:
            if num in arr2_with_idx:
                arr.append((arr2_with_idx[num], num))
            else:
                arr.append((n, num))
        
        arr.sort(key = lambda x:(x[0], x[1]))

        return [num for _, num in arr]

 

arr1의 요소들을 arr2의 순서대로 정렬하고, arr2에 없는 요소들은 오름차순으로 뒤에 배치하면 되는 문제였다.

 

arr2_with_idx 딕셔너리를 활용하여 문제를 해결했다.

 

먼저, arr2에 있는 num과 idx를 key-value 쌍으로 딕셔너리에 저장해놓았다.

 

그리고 arr이라는 새로운 리스트를 만들었고, arr에는 arr1의 각 num과 처음에 저장했던 arr2_with_idx[num]의 값을 튜플 형태로 저장했다.

 

예를 들어, Input이 arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] 와 같을 때, arr2_with_idx에 2:0. 1:1, 4:2 ... 으로 저장될 것이고, arr에는 (0, 2), (3, 3) ... 과 같이 저장될 것이다.

 

만약 arr2_with_idx에 없는 수들은 arr2의 길이와 함께 튜플로 저장했다. ex) (6, 19), (6, 7)

 

그렇다면 arr에는 다음과 같이 저장될 것이다. 

 

이제 이를 튜플에 첫번째 값을 기준으로 정렬을 시킨다. 만약 첫번째 값이 같다면 두번째 값으로 정렬하면 된다.

 

arr.sort(key = lamda x:(x[0], x[1]))와 같이 할 수 있다. 결과는 다음과 같이 나온다.

 

이제 튜플에 두번째 값만을 가지고 리스트를 만들어 결과를 반환하면 된다. (return [num for _, num in arr])

 

---

1122. Relative Sort Array