•
문제 설명 : 제공되는 두 배열에서 공통되는 요소는 조건에 맞게 앞에 설정하고, 공통되지 않은 요소는 뒤에 붙어준다
•
풀이 방법
◦
요소 관리는 hash table을 사용하였으며, 마지막 오름차순으로 붙어줄 때만 sorted를 사용하였다.
•
시간복잡도 :
•
성공 코드
from collections import defaultdict
class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
arr1_count_info = defaultdict(int)
# O(N)
arr1_set, arr2_set = set(arr1), set(arr2)
result = []
# arr1에 존재하는 요소들과 각 숫자의 갯수 확인 -> O(N)
for item in arr1:
arr1_count_info[item] += 1
# arr2에 있는 요소를 확인한다. -> O(N)
for item in arr2:
for _ in range(arr1_count_info[item]):
result.append(item)
# arr2에 존재하지 않는 요소만 남기기 위해 remove 한다.
arr1_set.remove(item)
# 남아있는 요소를 추가한다.
# sorted -> O(NlogN)
for item in sorted(arr1_set):
for _ in range(arr1_count_info[item]):
result.append(item)
return result
Python
복사
