List Subtraction

두 개의 리스트 $x, y$가 있을 때 $x$ 리스트 원소 중 $y$ 리스트에 속한 원소를 제거하고 싶습니다. 예를 들면 다음과 같은 빼기 연산 (-)를 수행하고 싶은겁니다.

>>> x = [1,2,3,4,5,6,7,8,9,0]  
>>> x  
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]  
>>> y = [1,3,5,7,9]  
>>> y  
[1, 3, 5, 7, 9]  
>>> x - y   # (should return [2,4,6,8,0])

하지만 리스트 자료구조에 대해서는 빼기 연산 (-)를 지원하지 않으므로 다음과 같은 에러가 발생합니다.

Traceback (most recent call last):
  File "<input>", line 1, in <module>
TypeError: unsupported operand type(s) for -: 'list' and 'list'

이 상황에서 생각할 수 있는 방법으로는 집합 (set)를 이용하는 겁니다. 파이썬의 set는 중복된 원소를 포함시키지 않으므로 $x$ 원소 중 $set(y)$에 포함되지 않은 원소만 추려내면 됩니다. 또한, 빼기 연산 (-)을 위해 __sub__ 메소드를 다음과 같이 정의할 수 있습니다.

class MyList(list):
    def __init__(self, *args):
        super(MyList, self).__init__(args)
    def __sub__(self, other):
        return list(itertools.filterfalse(set(other).__contains__, self))

• itertools 모듈의 filterfalse(함수, iterable) 함수는 인자로 들어온 iterable 객체를 순회하면서 인자로 주어진 함수의 결과가 False인 것만 리턴합니다.

하지만 이 경우는 $x$에 중복된 원소가 들어있고 그 원소가 $y$에 속할 때 중복된 것을 모두 제거하게 됩니다.

x = MyList(1,2,3,2,2,4)
y = MyList(2,5,2)
>>> x-y
[1, 3, 4] # Want [1,3,2,4]

---

우리가 원하는 것은 1) $x$의 순서를 유지하고, 2) 중복된 것을 $y$에 포함된 횟수만큼 제거하면서, 3) 시간복잡도를 최소화하는 것입니다. ($x, y$ 길이를 각각 $n, m$이라 했을 때, for문을 $x,y$에 대해 중첩하면 시간복잡도가 $O(mn)$이 되고 목표는 $O(m+n)$이 되어야합니다.) 2번에 포커싱을 두고 collections 모듈의 Counter 클래스를 이용해 보겠습니다. Counter에 리스트를 입력으로 넣으면 {원소: 원소 출현 횟수} 딕셔너리 형태가 리턴됩니다. 따라서 $y$를 Counter에 넣고 $x$ 리스트를 순회하면서 $x$의 원소가 $y$에 속할 경우 $y$ Counter에서 횟수를 하나 줄여주는 방식으로 구성할 수 있습니다.

from collections import Counter

x = [1,2,3,2,2,4]
y = [2,5,2]

remaining = Counter(y)

out = []
for val in x:
    if remaining[val]:
        remaining[val] -= 1
    else:
        out.append(val)

• $x, y$ 길이를 각각 $n, m$이라 했을 때 $y$의 Counter를 구성하는 것은 $O(m)$ 시간복잡도가 소요됩니다.
• $x$의 반복문을 수행할 경우 $O(n)$ 시간복잡도가 소요되는데, Counter 객체는 딕셔너리이므로 조회에 $O(1)$, 리스트의 append는 amortized되어 $O(1)$이 소요됩니다.
• 따라서 총 시간복잡도는 $O(m+n)$이 되게 됩니다.

>>> out
[1, 3, 2, 4]

마지막으로 Counter 객체에 빈 Counter 객체를 더하면 value가 0이나 음수인 키를 제거하는 트릭을 이용하면 $y$에 어떤 원소가 남았는지 확인할 수 있습니다.

remaining += Counter()
remaining
Counter({5: 1})

 

참조

• https://stackoverflow.com/questions/3428536/python-list-subtraction-operation/57827145#57827145