[코딩 알고리즘] LeetCode - 219. Contains Duplicate II 해시테이블 마스터하기

안녕하세요 🚀 오늘은 코딩 테스트에서 자주 마주치는 문제 중 하나인 '중복 요소 찾기' 문제를 파이썬으로 어떻게 풀 수 있는지 함께 알아보려고 해요. 이 문제는 배열과 인덱스를 다루는 능력을 시험하는 좋은 예제랍니다.

 

해시테이블

 

 

---

문제 설명

주어진 문제는 정수 배열 nums와 정수 k가 주어졌을 때, nums[i] == nums[j]이면서 abs(i - j) <= k를 만족하는 서로 다른 두 인덱스 i, j가 존재하는지 확인하는 것입니다. 즉, 배열 안에서 최대 k만큼 떨어진 위치에 동일한 값을 가진 요소가 있는지 찾는 거죠. 🕵️‍♂️

 

릿코드 문제보러가기

---

알아야 할 개념: 해시 테이블

이 문제를 해결하기 위한 핵심 개념은 '해시 테이블'입니다. 해시 테이블은 키를 값에 매핑할 수 있는 데이터 구조로, 파이썬에서는 딕셔너리를 사용해 간단히 구현할 수 있어요. 해시 테이블은 검색, 삽입, 삭제가 매우 빠르다는 장점이 있죠. 🔑

---

문제 풀어보기

파이썬에서 해시 테이블을 이용하여 이 문제를 풀어보면 다음과 같습니다.

 

def containsNearbyDuplicate(nums, k):
    num_dict = {}
    for i, num in enumerate(nums):
        if num in num_dict and i - num_dict[num] <= k:
            return True
        num_dict[num] = i
    return False

# 예제 1
print(containsNearbyDuplicate([1,2,3,1], 3)) # True

# 예제 2
print(containsNearbyDuplicate([1,0,1,1], 1)) # True

# 예제 3
print(containsNearbyDuplicate([1,2,3,1,2,3], 2)) # False

 

코드를 보면 알 수 있듯, 배열을 순회하면서 현재 요소의 값이 이미 해시 테이블에 있는지 확인하고, 조건에 맞으면 True를 반환합니다. 만약 조건에 맞지 않으면, 해시 테이블을 업데이트하죠. 모든 요소를 확인해도 조건에 맞는 경우가 없으면 False를 반환합니다. 🔄

---

오늘 배운 '중복 요소 찾기' 문제 해결법은 파이썬의 해시 테이블(딕셔너리)을 이용한 간단하면서도 효과적인 방법이었습니다. 이 방법을 기억해두시면 코딩 테스트는 물론 실제 프로그래밍에서도 유용하게 사용할 수 있을 거예요. 코딩은 연습이 중요하니, 오늘 배운 내용을 잘 숙지해서 다음 코딩 테스트 때 꼭 활용해보세요! 👨‍💻🎉