leetcode : Find Original Array From Doubled Array

https://leetcode.com/problems/find-original-array-from-doubled-array/

Find Original Array From Doubled Array - LeetCode

 

엣지케이스 때문에 너무 어려운 문제였다. 구글문제인가..?;;

 

class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        numdict = Counter(changed)
            
        answer = []
        for num in sorted(list(numdict.keys())):
            while numdict[num] > 0:
                if numdict[num*2] > 0:
                    numdict[num*2] -= 1
                    numdict[num] -= 1
                    answer.append(num)
                else:
                    return []
            if numdict[num] < 0:
                return []
        
        return answer

 

이게 내 정리의 한계다

굵은 글씨 친 부분은 num이 0인 케이스 때문에 있는거.

 

key 정렬을 안하면 다음과 같은 케이스에 문제가 된다

매칭이 초록색처럼 되어야 한다. (1,2) (2,4) (4,8) (8,16) 근데 정렬 안하고 순회하게 되어서 4,4가 먼저 들어온다 치자. 어떻게 매칭할건가? 나보다 작은거부터 매칭하면 파란색으로 매칭돼서 잘못돼버리고 큰거부터 보면 빨간색처럼 매칭된다.

 

사람마다 예외를 다루는 방법이 제각각이어서 재밌는 문제였지만 해시테이블로 카운트하고 키를 정렬해서 푼다는 전체적인 방향은 다들 같았다.

    def findOriginalArray(self, A):
        c = collections.Counter(A)
        if c[0] % 2:
            return []
        for x in sorted(c):
            if c[x] > c[2 * x]:
                return []
            c[2 * x] -= c[x] if x else c[x] / 2
        return list(c.elements())