Code Review Professional

주요 문제는 중복 탐색이 불필요하게 반복되어 효율성이 매우 낮다는 점입니다.

리뷰 결과

현재 구현의 시간 복잡도는 O(n²)입니다.

for i in range(len(items)):
    for j in range(len(items)):

모든 원소 쌍을 비교하므로, 데이터가 20,004개인 예제에서는 약 4억 번의 비교가 발생할 수 있습니다. 또한 다음 검사도 리스트 선형 탐색이므로 추가 비용이 발생합니다.

items[i] not in duplicates

duplicates의 크기가 커질수록 이 검사 역시 느려집니다.

개선안

set을 사용해 이미 확인한 값과 중복 값을 추적하면 평균 시간 복잡도를 O(n)으로 줄일 수 있습니다.

def find_duplicates(items):
    seen = set()
    duplicates = set()

    for item in items:
        if item in seen:
            duplicates.add(item)
        else:
            seen.add(item)

    return list(duplicates)

원래 코드처럼 첫 등장 순서를 유지하려면 다음과 같이 작성할 수 있습니다.

def find_duplicates(items):
    seen = set()
    duplicates = []

    for item in items:
        if item in seen and item not in duplicates:
            duplicates.append(item)
        seen.add(item)

    return duplicates

다만 두 번째 구현은 duplicates에 대한 리스트 탐색 때문에 최악의 경우 다시 비효율적일 수 있습니다. 순서 보존과 효율성을 모두 원한다면 별도의 집합을 함께 사용하는 것이 좋습니다.

def find_duplicates(items):
    seen = set()
    duplicate_values = set()
    duplicates = []

    for item in items:
        if item in seen and item not in duplicate_values:
            duplicate_values.add(item)
            duplicates.append(item)
        seen.add(item)

    return duplicates

이 구현은 평균 O(n) 시간과 O(n) 추가 공간을 사용하며, 입력 예제의 결과는 다음과 같습니다.

[5, 100]

단, set을 사용하므로 원소는 해시 가능한 타입이어야 합니다. 리스트나 딕셔너리처럼 해시할 수 없는 객체를 처리해야 한다면 다른 방식이 필요합니다.