[leetCode] 1122. Relative Sort Array (Python)

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 don't 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]

 

Constraints:

• arr1.length, arr2.length <= 1000
• 0 <= arr1[i], arr2[i] <= 1000
• Each arr2[i] is distinct.
• Each arr2[i] is in arr1.

Solution

from collections import Counter

class Solution:
    def relativeSortArray(self, arr1, arr2):
        temp1 = []
        temp2 = []
        
        cnt = Counter(arr1)
        
        for num in arr2:
            if num in arr1:
                temp1 = temp1 + [num] * cnt[num]
        
        temp2 = sorted([num for num in arr1 if num not in arr2 ])
        
        return temp1 + temp2

Solution 해설

먼저 arr1의 리스트에 각각의 값이 몇 개씩 존재하는지 collections의 Counter를 활용하여 개수를 세어줍니다.

sort order 기준으로 준 arr2를 활용해서 기준이 있는 값부터 왼쪽에 정렬되어 나오도록

arr2의 값 x 카운팅한 개수를 바탕으로 먼저 temp1에 넣어줍니다.

 

그 다음 기준이 없는 값들만 temp2에 남긴 다음 오름차순으로 정렬한 후에

 

temp1 리스트와 temp2 리스트를 합하여 return 합니다.

SOMJANG/CODINGTEST_PRACTICE