[LeetCode] 2007 | Find Original Array From Doubled Array | Python

---

문제 링크: https://leetcode.com/problems/find-original-array-from-doubled-array/

---

문제

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.

---

조건

• 1 <= changed.length <= $10^5$
• 0 <= changed[i] <= $10^5$

---

내 풀이

doubled array 여부를 확인하기 위해서는 어떤 값과 그 값의 두배되는 값을 모두 주어진 array(changed)에서 제거할 수 있어야한다.

이를 효과적으로 하기 위해서는 오름차순으로 array를 정렬한 뒤 진행하면 된다.

가장 작은 수부터 차례로, 해당 숫자(ex. 2)의 두배되는 값(ex. 4)을 doubled라는 dict에 저장한다.

만약 이미 그 숫자(ex. 4)가 doubled라는 dict에 있다면 그 숫자의 절반(ex. 2)에 해당하는 수가 주어진 array(changed)에 존재한다는 것이기 때문에, 그 숫자의 절반(ex. 2)에 해당하는 수를 ans에 추가한다.

 

주어진 array 안의 모든 원소에 대해서 해당 과정을 진행한 후 doubled에 값이 남아있다면 해당 array는 doubled array가 아니기 때문에 []를 리턴하고, 그렇지 않은 경우에는 ans를 리턴한다.

---

코드

class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        ans = []
        doubled = defaultdict(int)
        
        for num in sorted(changed):
            if num in doubled:
                doubled[num] -= 1
                
                if doubled[num] == 0:
                    del doubled[num]
                
                ans.append(num//2)
            
            else:
                doubled[num*2] += 1
                
        if len(doubled) > 0:
            return []
        
        return ans