LeetCode

LeetCode 217 Contains Duplicate 풀이: 해시 집합으로 중복 검사

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

모든 원소를 한 번씩 확인하면서 이미 본 값인지 검사하면 되는 기본적인 해시 집합 문제다. 중복을 발견면 즉시 종료할 수 있고 구현과 예외 처리가 단순하므로 Level 1로 판단했다.

1. 문제 요약

정수 배열 nums가 주어질 때, 어떤 값이라도 두 번 이상 등장하면 True, 모든 값이 서로 다르면 False를 반환한다.

중요 조건은 다음과 같다.

  • 배열 길이는 1 이상 10^5 이하다.
  • 각 값은 -10^9 이상 10^9 이하다.
  • 같은 값이 여러 위치에 등장할 수 있다.
  • 중복을 하나라도 찾으면 나머지 원소를 확인하지 않아도 된다.

예를 들어 [1,2,3,1]에서는 1이 두 번 등장하므로 True이고, [1,2,3,4]는 모든 값이 다르므로 False다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

해시 집합 상태

seen 집합에 지금까지 확인한 숫자를 저장한다. 배열을 왼쪽부터 순회하면서 다음 순서로 처리한다.

  1. 현재 숫자가 seen에 있으면 이미 등장한 값이므로 True를 반환
  2. 현재 숫자가 처음 등장했다면 seen에 추가
  3. 배열을 끝까지 확인했는데 중복이 없으면 False를 반환.

집합의 원소 조회와 삽입은 평균적으로 O(1)이므로 각 숫자를 빠르게 확인할 수 있다.

중복 확인을 삽입보다 먼저 하는 이유

중복 여부를 판단하려면 현재 숫자가 과거에 등장했는지만 알면 된다. 과거의 모든 원소를 다시 비교할 필요 없이, set를 사용한다.

중복을 발견한 순간 즉시 True를 반환한다. 중복이 배열 앞부분에 있으면 뒤의 원소들을 확인하지 않아도 된다.

상태 전이와 경계 처리

nums = [4, 7, 2, 4]

읽은 값 4: seen = {}
4 추가:  seen = {4}
읽은 값 7: seen = {4, 7}
읽은 값 2: seen = {2, 4, 7}
읽은 값 4: 이미 존재 -> True

배열 길이는 최소 1이므로 빈 배열 분기는 필요하지 않다. 원소가 하나뿐이면 한 번 집합에 추가한 뒤 끝까지 중복이 발견되지 않아 False를 반환한다.

오답 접근과 반례

각 원소를 다른 모든 원소와 비교하면 결과는 구할 수 있지만 최악의 경우 같은 비교를 반복해 O(n^2) 시간이 필요하다.

nums = [1, 2, 3, ..., 100000]

모든 값이 서로 다르면 가능한 쌍을 거의 모두 비교하게 된다. 입력 길이가 10^5까지 가능하므로 모든 쌍을 확인하는 방식은 비효율적이다.

정렬 후 인접한 값만 비교하는 방법도 가능하지만, 원본 배열의 순서를 바꾸고 정렬에 O(n log n) 시간이 필요하다. 집합을 사용하면 정렬 없이 평균 O(n)에 해결할 수 있다.

시간·공간 복잡도

배열을 최대 한 번 순회하고 집합 조회와 삽입은 평균 O(1)이므로 평균 시간 복잡도는 O(n)이다. 최대 n개의 값을 집합에 저장하므로 공간 복잡도는 O(n)이다.

3. 문제 해결 코드 (Python)

현재 값을 집합에 넣기 전에 먼저 확인해야 한다. 먼저 추가한 뒤 확인하면 현재 값을 자기 자신과 중복으로 판단하게 된다.

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        seen = set()

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

        return False

number in seen으로 기존 등장 여부를 확인한 뒤, 처음 보는 값만 seen.add(number)로 추가한다. 중복이 발견되면 즉시 True를 반환하고, 끝까지 중복이 없으면 False를 반환한다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 중복 유무와 중복 위치가 다른 사례를 확인할 수 있다.

solver = Solution()
assert solver.containsDuplicate([1, 2, 3, 1]) is True
assert solver.containsDuplicate([1, 2, 3, 4]) is False
assert solver.containsDuplicate([1, 1, 1, 3, 3, 4, 3, 2, 4, 2]) is True

4. 공식 예제와 추가 검증

작성한 containsDuplicate 함수를 Python으로 실행해 공식 예제와 중복 위치·경계 값을 확인했다.

공식 예제

입력 기대 출력 확인 결과
nums = [1,2,3,1] True 통과
nums = [1,2,3,4] False 통과
nums = [1,1,1,3,3,4,3,2,4,2] True 통과

추가 검증 1: 원소 하나

입력: nums = [7]
기대 출력: False
확인 결과: 통과
검증 목적: 중복이 생길 수 없는 최소 배열 확인

추가 검증 2: 첫 번째와 마지막 값이 같은 경우

입력: nums = [4,8,2,9,4]
기대 출력: True
확인 결과: 통과
검증 목적: 배열의 먼 위치에 있는 중복도 찾는지 확인

추가 검증 3: 음수와 0의 중복

입력: nums = [-3,0,5,-3]
기대 출력: True
확인 결과: 통과
검증 목적: 값의 부호와 관계없이 같은 정수를 중복으로 처리하는지 확인

추가 검증 4: 큰 값이 모두 다른 경우

입력: nums = [-1000000000, 0, 1000000000]
기대 출력: False
확인 결과: 통과
검증 목적: 허용된 값 범위의 양끝을 처리하는지 확인

5. 다른 풀이 방식 검색 및 비교

정렬 방식은 배열을 정렬한 뒤 인접한 두 값이 같은지 확인하므로 추가 집합 공간을 사용하지 않을 수 있다. 하지만 정렬 때문에 O(n log n) 시간이 필요하고 원본 배열의 순서가 바뀔 수 있다.

집합 방식은 값을 처음 확인했는지 평균 O(1)에 판정하므로 O(n) 시간에 동작한다. 대신 이미 본 값을 저장해야 해 O(n) 공간을 사용한다. 이 글에서는 입력 크기가 최대 10^5이고 빠른 중복 판정이 목표이므로 집합 방식을 선택했다.

마무리

Contains Duplicate는 현재 값이 이전에 등장했는지만 확인하면 되는 기본 해시 문제다. 이미 본 값을 set에 저장하고, 집합에 있는 값을 다시 만나면 즉시 True를 반환하면 된다. 정렬 없이 평균 O(n) 시간과 O(n) 공간으로 중복 여부를 판정할 수 있다.

관련 문제

#해시#LeetCode#난이도 1