배열 중복 체크하기 (이중배열/ set)
배열 중복 체크하기 (이중배열/ set) — #LeetCode #개발자의도구들 #배열중복 #이중배열중복체크 #set only 파이썬 목표 참고 : 여기 내가 생각...
#LeetCode#Naver Blog
#LeetCode #개발자의도구들 #배열중복 #이중배열중복체크 #set
- only 파이썬
- 목표 참고 : 여기
내가 생각한 로직
투 포인터 3Sum 문제를 풀다가 중복 여부 검사가 필요해서 어떻게 중복 체크를 할까 고민하다가. O(n) 로직을 생각했었다.
def is_distinct(self, list1, list2):
print("test list1, list2", list1, list2)
test = {}
for e in list1:
test[e] = 1 if e not in test else test[e] + 1
print("set test", test)
for e in list2:
if e not in test:
return True
test[e] -= 1
print("updated test", test)
for v in test.values():
if v != 0:
return True
# v가 하나라도 0이 아니면 True
# 이후는 모두 False
return False
- list1, list2는 각각 개별 하나의 리스트이고, 각각 요소를 map의 key로 사용하여 중복 여부를 테스트한다.
- 이 방법은 단순하지만 매우느리다.
- 이중 배열의 경우 전체 배열에 대해서 테스트하고 또 전체 요소를 테스트해야하기 때문에 O(n²)이라는 시간 복잡도를 가지게된다.
- ☠️ 기존에 O(n)이라고 잘못 계산을 했다...
좀 더 효율적인 방법이 없나?
3Sum의 경우에는 궂이 중복을 확인하지 않아도 문제가 풀리는 문제였다. 하지만, 이런류의 문제는 언제 나와도 이상하지 않기 때문에 확실하게 로직을 알고 넘어가고 싶었다.
그래서 이번기회에 공부한 것을 정리하였다.
생각했던 여러가지 오답들
☠️ 배열 자체를 set()에 넣어서 관리?
>>> []을 key로 hash할 수 없어서 불가능하다.
♟️✅ 앞으로는 이렇게 사용하자.
✅ Counter를 사용하자
>>> 표준 라이브러리로 코딩 테스트에서 사용이 가능하다.
✅ 이 상황에서 가장 빠른 시간 복잡도는 O(n * k)이다.
>>> 놀랍게도 내가 생각한 로직이 최선의 방법이었다...
♟️ 정렬 후 비교 : O(n * klogk)
♟️ Counter사용하여 비교: O(n * k)
# 정렬 후 비교
def is_distinct(list1, list2):
return sorted(list1) != sorted(list2)
# Counter 사용
from collections import Counter
def is_distinct(list1, list2):
return Counter(list1) != Counter(list2)