View in English →

Code › algorithm-study

LeetCode 217 - Contains Duplicate

중복 원소 확인 문제를 brute force, sorting, hash set 관점에서 비교한 풀이

algorithmleetcodearrayhash-setsortingpythonlearning

이 문제는 Easy 난이도의 배열 문제다. 정수 배열이 주어졌을 때 같은 값이 두 번 이상 등장하면 true를 반환하고, 모든 값이 한 번씩만 등장하면 false를 반환하면 된다. 이번 글에서는 brute force, sorting, hash set 세 가지 풀이를 시간복잡도와 공간복잡도 관점에서 비교했다.

문제 링크 & 설명

  • 문제 링크: 217. Contains Duplicate
  • 요약: 정수 배열 nums가 주어졌을 때, 배열 안에 중복된 값이 하나라도 있으면 true를 반환하고, 없으면 false를 반환하는 문제다.

예를 들어 배열이 이렇게 주어진다고 해보자.

nums = [1, 2, 3, 1]

1이 두 번 등장하므로 결과는 true다. 반대로 [1, 2, 3, 4]처럼 모든 값이 한 번씩만 나온다면 false를 반환한다.

문제 자체는 단순하지만, 풀이를 비교해보면 시간과 공간을 어디에 쓰는지가 잘 보인다. 모든 쌍을 비교하면 추가 메모리는 거의 쓰지 않지만 시간이 커지고, set을 쓰면 시간을 줄이는 대신 입력 크기에 비례하는 메모리를 사용한다.

접근 방법

이제부터는 ML쪽 생태계에 익숙해지기 위해 코테도 파이썬으로 코드를 작성하려고 한다 ㅎㅎ

1. brute force로 모든 쌍 비교

가장 직접적인 방법은 모든 쌍을 비교하는 것이다. 첫 번째 원소와 나머지를 비교하고, 두 번째 원소와 그 뒤의 원소들을 비교하는 식이다.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] == nums[j]:
                    return True

        return False

이 풀이는 별도의 자료구조를 만들지 않으므로 추가 공간은 O(1)로 볼 수 있다. 대신 비교 횟수가 빠르게 늘어난다. 원소가 n개라면 대략 n²에 가까운 쌍을 확인해야 하므로 시간복잡도는 O(n²)이다.

2. 정렬 후 인접 원소 비교

시간복잡도를 brute force보다 줄이는 다른 방법은 정렬이다. 배열을 정렬하면 같은 값들은 서로 붙게 되므로, 정렬 후에는 인접한 원소만 비교하면 된다.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()

        for i in range(len(nums) - 1):
            if nums[i] == nums[i + 1]:
                return True

        return False

정렬 비용 때문에 시간복잡도는 O(n log n)이고, 모든 쌍을 비교하는 O(n²)보다는 훨씬 낫다. 중복 검사 자체는 정렬 이후 한 번의 선형 순회로 끝난다.

여기서 헷갈릴 수 있는 부분은 공간복잡도였다. Python의 list.sort()는 리스트를 제자리에서 정렬하므로 겉으로는 추가 배열을 만들지 않는 것처럼 보이지만, 정렬 알고리즘인 Timsort는 최악의 경우 입력 크기에 비례하는 공간을 사용할 수 있다. 그래서 이 풀이의 추가 공간을 보수적으로 O(n)으로 잡았다.

C++의 std::sort처럼 보통 O(log n) 정도의 stack 공간으로 설명하는 정렬과는 다르게 볼 필요가 있었다. 같은 “정렬해서 푼다”는 접근이라도 언어와 런타임의 정렬 구현에 따라 공간복잡도 설명이 달라질 수 있다.

3. hash set으로 이미 본 값 확인

내 기준으로 가장 먼저 떠오른 방식은 루프를 돌며 이미 본 값을 set에 저장하는 방식이다. 배열을 왼쪽부터 보면서 현재 값이 이미 set 안에 있으면 중복을 찾은 것이므로 바로 true를 반환하고, 없으면 set에 추가한다.

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

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

        return False

이 방식은 중복이 하나라도 존재하는지를 앞쪽에서부터 체크하므로 순회하다가 중복이 발견되면 바로 반환할 수 있고, 최악의 경우에도 배열을 한 번만 순회하게 된다.

다만 set에는 지금까지 본 값을 저장해야 하므로 추가 공간이 필요하다. 모든 값이 서로 다르다면 set에는 결국 n개의 값이 들어간다.

복잡도 분석

1. brute force

  • 시간 복잡도: O(n²)

    • 모든 원소 쌍을 비교하기 때문에 입력이 커질수록 비교 횟수가 제곱으로 증가한다.

  • 공간 복잡도: O(1)

    • 별도의 자료구조를 만들지 않고 인덱스 변수만 사용한다.

2. sorting

  • 시간 복잡도: O(n log n)

    • 정렬이 가장 큰 비용이고, 이후 인접 원소 비교는 O(n)이다.

  • 공간 복잡도: O(n)

    • Python의 Timsort는 최악의 경우 입력 크기에 비례하는 공간을 사용할 수 있으므로, 최악의 경우 O(n)으로 본다.

3. hash set

  • 시간 복잡도: O(n)

    • 각 원소를 한 번씩 보면서 set 확인한다. 평균적으로 원소 확인과 insert는 O(1)로 볼 수 있다.

  • 공간 복잡도: O(n)

    • 모든 값이 서로 다르면 set에 n개의 값이 저장된다.

최적화 코드

이 문제에서는 hash set을 사용하는 방식이 가장 자연스럽다. 중복 여부만 확인하면 되므로, 지금까지 본 값만 기억하면 충분하다.

from typing import List

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

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

        return False

요약 및 회고

이 문제는 중복 확인이라는 단순한 요구사항을 세 가지 방식으로 비교하기 좋았다. brute force는 추가 메모리를 거의 쓰지 않지만 시간이 너무 커지고, sorting은 그보다는 시간을 줄이지만 정렬 비용을 고려해야 한다. hash set은 추가 메모리를 쓰는 대신 가장 직관적으로 이미 본 값인지를 판단한다.

이번 문제를 풀면서 Python의 sort도 C++의 std::sort와 비슷하게 생각했는데, Timsort는 최악의 경우 O(n) 공간을 사용할 수 있다고 한다. 알고리즘 풀이에서 정렬을 선택할 때는 O(n log n) 시간만 볼 게 아니라, 사용 중인 언어의 정렬 알고리즘과 복잡도를 함께 확인해 보는 것이 좋을 것 같다.