[Leetcode] #219 Contains Dup II
문제는 위와 같다. 즉,
- 주어진 리스트에서 같은 값의 서로 다른 인덱스가 있고, 그 인덱스의 차를 절댓값 한 값이 k보다 작으면 True, 그렇지 않으면 False 반환.
코드 :
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
dict = {}
for idx in range(len(nums)):
if nums[idx] in dict and abs(idx - dict[nums[idx]]) <= k:
return True
dict[nums[idx]] = idx
return False
- 처음 해야 할 일이 뭐지? 같은 값을 가진 서로 다른 두개의 인덱스를 찾는 것. -> 처음 조건문에서 찾고자 하는 값이 이미 딕셔너리 안에 있는지부터 확인한다; 만약 나타난다면, 같은 값이 두번 나타난다는것과 같다(첫번째 조건 nums[i] == nums[j] 만족). 만약, 이미 딕셔너리 안에 추가된 값이 아니라면 dict[nums[idx]] = idx를 통해 딕셔너리 안에 키-값 쌍을 추가해 준다.
- 일단 이 문제의 조건은 두가지다. 첫번째, 같은 값을 가진 요소가 리스트 안에 두개 이상 존재하는지. 두번째, 그 두개의 인덱스의 값을 빼고, 절댓값을 취했을때 파라미터로 주어진 k보다 작거나 같아야 함.
- 그렇다면, 두번째 조건문은 첫번째 조건문이 통과하기 전까진 의미가 없다. 일단 뺄셈을 하려면 우리는 피연산자 2개가 필요하고, 피연산자 2개가 존재하지 않는다면(리스트 안에 중복된 값이 없는 경우), 뒤의 조건은 확인할 필요 조차 없으므로 첫번째 조건을 조건문의 첫번째 조건으로 넘겨준다(첫번째 조건이 fail하면 곧바로 반복문을 빠져나가도록).
- 그 다음, 만약 첫번째 조건문이 통과가 된다면(중복된 요소를 찾았다면, 절댓값 계산을 한후 True or False를 반환한다.
엄청 쉽다. 코드를 보고 설명을 보면 아! 하고 바로 이해하겠지만, 아무런 정보 없이 문제를 풀었다면 어떻게 접근했을지부터 고민을 했을 것이다. 먼저, 중복된 값을 찾는데 딕셔너리(해시맵)를 쓰는 이유부터 알아보자.
- 빠른 조회 시간:
해시맵은 평균적으로 O(1) 시간 복잡도로 키-값 쌍을 조회할 수 있다. 이는 매우 빠른 시간에 특정 값이 해시맵에 존재하는지 확인할 수 있음을 의미한다.(중복값,,,)
배열을 순회하면서 각 요소를 해시맵에 저장하고 조회하면, 중복값을 매우 빠르게 찾을 수 있다.
- 고유한 키 저장:
해시맵은 키-값 쌍을 저장하므로, 각 요소의 인덱스를 값으로 저장하고 요소 자체를 키로 사용할 수 있다. 이를 통해 특정 값이 이미 해시맵에 존재하는지 쉽게 확인할 수 있다.
해시맵 이외에도 중복값을 찾기 위해 사용할 수 있는 몇 가지 자료구조가 있다(내가 처음에 중복된 값을 보자마자 생각난건 집합이다). 각 자료구조의 장단점을 비교해 보겠다.
-집합(Set):
장점: 중복 요소를 자동으로 제거한다. 해시맵과 마찬가지로 O(1) 시간 복잡도로 요소를 추가하고 확인할 수 있다.
단점: 요소의 인덱스를 저장할 수 없다. 인덱스 정보를 필요로 하는 문제에서는 적합하지 않다.(순서 x) 파이썬의 리스트(배열)는 순서(index)가 있는 sequiental 자료구조임. 메모리적인 관점에서 보면 리스트(배열)는 연속된 메모리 공간을 차지한다.
-정렬된 배열/리스트:
장점: 중복 요소를 찾기 위해 이진 탐색을 사용할 수 있다.
단점: 요소를 추가하거나 정렬하는 데 O(n log n). 특히 실시간으로 데이터가 변경되는 경우 비효율적이다.
-링크드 리스트(Linked List):
장점: 요소를 추가하는 데 O(1) 시간이 소요된다.
단점: 중복 요소를 찾기 위해 전체 리스트를 순회해야 하므로 O(n). 해시맵에 비해 비효율적이다.