[코테 연습] Relative Sort Array

https://leetcode.com/problems/relative-sort-array/

Relative Sort Array - LeetCode

---

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.

 

푸는데 걸린 시간: 5분

푼건 5분만에 풀었다... 음.. 시간 복잡도가 O(n^2)라.. 다르게 풀 수 없을까.. 

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        res = []
        for num in arr2:
            for num2 in arr1:
                if num == num2:
                    res.append(num2)
        rem = sorted([i for i in arr1 if i not in arr2])
        return res+rem

 

음.. dict이랑 Counter로 풀었지만,, 그렇게 차이가 안나는군..하긴 Counter를 하려면 또 배열을 돌긴해야하니까..?

미쳐가ㅣㅈ고 for문 안에 Counter를 넣었구나..

 

	from collections import Counter
	class Solution:
	def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
	res = []
	for i in arr2:
	res.extend([i] * Counter(arr1)[i])
	return res + sorted([i for i in arr1 if i not in res])

view raw Relative Sort Array.py hosted with ❤ by GitHub

 

집중해서 풀자.. 확실히 시간은 준다.

 

	from collections import Counter
	class Solution:
	def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
	res = []
	arrC = Counter(arr1)
	for i in arr2:
	res.extend([i] * arrC[i])
	return res + sorted([i for i in arr1 if i not in res])

view raw Relative Sort Array.py hosted with ❤ by GitHub