LeetCode: 1122. Relative Sort Array

문제

출처: LeetCode 

이 문제는 비교적 간단하다. 좋아요도 많다. 이것은 문제가 모호함이 없이 명쾌하다는 것이다. 문제를 요약하자면 다음과 같다. arr1, arr2 두개의 배열이 있다. arr1을 arr2의 기준으로 sorting하는 것이다. arr2의 모든 원소는 arr1에 포함되어있다. 하지만 arr1에는 arr2에 없는 원소도 있다. 이때, 이 원소들은 오름차순으로 sorting 된 arr1의 뒤에 붙이는 것이다. 위의 예제를 보면 이해가 된다. 이 문제에서 주의 할 점은 arr1에 같은 원소가 복수개로 주어질 수 있다는 것이다. 이것들은 sorting될 때 나란히 놓이게 되는 것이다. 

 

세가지 방법으로 코딩을 해봤다. 목표는 효율성을 증가시켜 런타임을 줄이는 것이다. 

solution 1  (Runtime: 40ms, faster than 49%)  

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        d = {}
        for n in arr1: 
            if n in d: 
                d[n] +=1 
            else: 
                d[n] = 1

        temp = []
        for i,n in enumerate(arr1): 
            if n in arr2: 
                if d[n] -1 > 0:  
                    ind = arr2.index(n)
                    arr2 = arr2[0:ind+1] + [n] + arr2[ind+1:]
                    d[n] = d[n] -1 

            else: 
                temp.append(n)


        return arr2 + sorted(temp)    

 

solution 2 (Runtime: 40ms, faster than 49.15%)

collections.Counter() 매서드를 이용해 arr1에 대한 해쉬테이블을 만들어 보았다. 이것은 첫 번째 방법에 비해 크게 런타임을 줄이지 못하였다. 

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        d = Counter(arr1)

        temp = []
        for n in arr1:
            if n not in arr2: 
                temp.append(n)

        ans = []
        for n in arr2: 
            if n in d: 
                ans = ans + [n]*d[n]

        return ans + sorted(temp)    

 

solution 3 (Runtime: 24ms, faster than 99%)  

세번째 방법에서는 arr2에 없는 원소들을 모으는 과정을 없애고, 최종 결과를 얻는 과정에 통합시켰다. 이때, arr1에서 사용된 원소를 삭제하는 방법으로 시도해 보았다. 이 과정이 끝나고 나면 arr1에 남아있는 값들은 arr2에 없는 원소들이다. 이것을 sorting해서 리턴할 결과뒤에 붙여주기만 하면 된다. 

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        d = Counter(arr1)

        ans = []
        for n in arr2: 
            if n in d: 
                ans = ans + [n]*d[n]
                for i in range(d[n]):
                    arr1.remove(n)

        return ans + sorted(arr1)