LeetCode: “Contains Duplicate” 문제

Source: Dev.to

Problem Statement

“이 리스트에 같은 숫자가 두 번 이상 등장하나요?”

모두가 이해할 수 있는 예시:

• [3, 7, 1, 9] → false
• [3, 7, 3, 9] → true
• [5] → false
• [8, 8] → true
• [] → false

어떤 숫자가 두 번 이상 나타나는지를 신뢰성 있게 감지하는 방법이 필요합니다.

Naïve Human Approach

리스트 [4, 1, 7, 2, 9, 4, 8] 를 생각해 보세요.

1. 4 를 가져와서 기억한다
2. 1 을 가져와서 새롭다 → 기억한다
3. 7 을 가져와서 새롭다 → 기억한다
4. 2 를 가져와서 새롭다 → 기억한다
5. 9 를 가져와서 새롭다 → 기억한다
6. 4 를 가져와서 중복!

알고리즘: 본 적 있는 숫자를 기억해 두고, 이미 기억에 있는 숫자를 만나면 멈춘다.

Naïve Python Implementation

def has_duplicate(nums):
    seen = []                # empty list = our memory

    for num in nums:         # look at each number one by one
        if num in seen:      # is it already in memory?
            return True      # yes → duplicate found
        seen.append(num)     # no → remember it

    return False             # no duplicates

Mental Run

입력: [4, 1, 7, 4] → True 를 반환합니다.

Complexity Issue

리스트에서 num in seen 를 확인하면 각 요소를 스캔하므로 O(n) 시간이 듭니다.
n 개 요소에 대해 루프를 돌면 전체 시간 복잡도는 O(n²) 가 되며, 이는 큰 입력(예: 100,000개 요소)에는 허용되지 않습니다.

Optimized Solution with a Set

Python set 은 거의 상수 시간으로 멤버십 테스트를 제공합니다(해시 테이블 조회).

def has_duplicate(nums):
    seen = set()             # fast lookup structure

    for num in nums:
        if num in seen:
            return True
        seen.add(num)

    return False

이제 알고리즘은 O(n) 시간과 O(n) 추가 공간으로 동작합니다.

Full LeetCode‑style Class

class Solution:
    def containsDuplicate(self, nums):
        seen = set()
        for num in nums:
            if num in seen:
                return True
            seen.add(num)
        return False

# Simple test
s = Solution()
nums = [1, 0, 2, 5, 8, 9, 1]
result = s.containsDuplicate(nums)
print(result)   # True

코드를 실행하면 기대한 출력이 확인됩니다.

Takeaways

• 올바른 자료구조 선택(list vs. set)이 성능에 큰 영향을 미칩니다.
• 시간 복잡도 이해는 확장 가능한 솔루션을 작성하는 데 도움이 됩니다.
• 인간의 논리를 효율적인 기계 논리로 변환하는 것이 알고리즘 문제 해결의 핵심 기술입니다.

이 교훈은 LeetCode를 넘어 다음에도 적용됩니다:

• API 설계
• 백엔드 시스템 최적화
• 대용량 데이터 처리
• 성능 병목 현상 방지

---

이번 주는 해시맵과 문자열에 집중하고 있습니다. 학습에 건배!