[2024] day 164. Leetcode 1122. Relative Sort Array

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

2024년 6월 11일 (화)
Leetcode daily problem

1122. Relative Sort Array

https://leetcode.com/problems/relative-sort-array/?envType=daily-question&envId=2024-06-11

Problem

두 개의 배열 arr1과 arr2가 주어진다.
arr2의 요소는 중복없는 각 하나의 서로 다른 정수형 요소로 구성되어 있고, arr2의 모든 요소는 arr1에 존재한다.

arr1에 있는 항목의 상대적 순서가 arr2와 동일하도록 arr1의 요소를 정렬한다. arr2에 나타나지 않는 요소는 arr1의 끝에 오름차순으로 배치한다.

예를 들어
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] 이다.

Solution

hash_map, sort

처음 구현은 주어진 arr1의 요소에 따른 횟수를 저장한 map을 만들고,
배열 arr2를 돌면서, 해당 arr1의 map에 해당하는 만큼 요소를 리스트로 더해준다. 탐색한 요소는 map에서 제거 해준다.

그리고 map의 key값을 기준으로 오름차순 한 후에
해당 map의 key값을 value 값에 따라 리스트에 추가해주는 방식이다.

Code

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        cnt_map = {}
        etc = []
        
        for a1 in arr1:
            cnt_map[a1] = cnt_map.get(a1, 0) + 1
        
        ans = []
        
        for a2 in arr2:
            ans.extend([a2] * cnt_map[a2])
            del cnt_map[a2]
        
        sorted_map = {k: cnt_map[k] for k in sorted(cnt_map)}
        
        for k,v in sorted_map.items():
            ans.extend([k]*v)
            
        return ans

Complexicity

시간 복잡도

arr1을 돌면서 map을 생성하는데 O(n) 이 소요되고, arr2를 순회하면서 반환할 결과 리스트에 추가하는데 O(mk)가 소요 된다.
나머지 map을 정렬하는데 O(klogk)가 소요되고, 해당 map을 순회하면서 ans에 추가하는 O(kv)가 소요된다.

최종 시간 복잡도는 O(n+mk+klogk+kv) 이다.

공간 복잡도

맵을 생성하고, 정렬된 맵을 만드는데 O(n)이 필요하고,
반환할 결과 리스트 O(n)이 필요해서 최종 공간 복잡도는 O(n) 이다.

---

해당 방법 외에 Counting Sort 방법을 사용한 솔루션이 있다.

주어진 arr1의 배열의 요소의 가장 큰 정수 만큼의 배열(여기서 cnt)을 생성한 후에,
arr1을 탐색하면서 해당 배열(cnt)의 요소의 인덱스 만큼 빈도수를 업데이트 한다.

그 후 arr2를 탐색하면서 해당 배열(cnt) 값 만큼 요소를 증가하고, 배열의 요소 값은 추가한만큼 -1 해가면서 업데이트 한다.

마지막으로 배열(cnt)을 한 번 더 탐색하면서 남은 배열의 요소만큼 결과에 추가해준다.

n을 arr1의 크기, m을 arr2의 크기, k를 arr1에서 가장 큰 요소라고 한다면,

시간 복잡도는

• arr1에서 최대 요소를 찾는 데 O(n)
• cnt 배열을 사용하여 arr1의 각 요소의 발생 횟수를 세는 데 O(n)
• arr2의 상대적 순서에 따라 결과 배열에 요소를 추가하는 데 O(m + n)
• cnt 배열을 순회하여 남은 요소를 결과 배열에 추가하는 데 O(n + k)

이 단계를 모두 합치면 전체 시간 복잡도는 O(n + n + m + n + k) = O(n + m + k)이다.

공간 복잡도는
cnt 배열의 크기는 maxElement + 1이므로, 이는 O(k) 공간을 차지하며 여기서 k는 arr1의 최대 요소이다.
최종 공간복잡도는 O(n) 이다.