입력 순서를 유지하며 중복 숫자 제거하기

중복을 제거할 때는 어떤 숫자를 남길지만큼 어떤 순서로 남길지도 중요하다. 예를 들어 [3, 1, 3, 2, 1]에서 각 숫자가 처음 등장한 순서를 유지하려면 결과는 [3, 1, 2]가 되어야 한다.

처음에는 리스트에서 직접 중복을 확인했고, 이후 집합을 거쳐 딕셔너리 키의 삽입 순서를 이용하는 방식으로 정리했다.

결과 리스트에서 중복 확인하기

첫 구현은 결과 리스트에 없는 숫자만 추가하는 방식이었다.

def unique_numbers(numbers):
    result = []
    for number in numbers:
        if number not in result:
            result.append(number)
    return result

입력을 앞에서부터 읽으므로 처음 나온 숫자가 그 순서대로 result에 담긴다. 다만 number not in result는 결과 리스트를 탐색한다. 입력이 n개이고 대부분 서로 다르면 확인할 리스트도 점점 길어져, 전체 시간 복잡도는 최악의 경우 O(n²)이다.

집합으로 바꾸면서 생긴 순서 문제

다음에는 중복 제거를 한 줄로 줄였다.

def unique_numbers(numbers):
    return list(set(numbers))

집합은 중복을 제거하지만 입력 순서를 보장하지 않는다. 따라서 결과를 다시 리스트로 만들어도 숫자가 처음 등장한 순서가 유지된다고 기대할 수 없다. 중복 제거는 간결해졌지만, 순서까지 지켜야 하는 목적에는 맞지 않는 변경이었다.

집합과 리스트의 역할 나누기

순서를 유지하면서 중복 확인도 빠르게 하기 위해 seen과 result를 함께 사용했다.

def unique_numbers(numbers):
    seen = set()
    result = []
    for number in numbers:
        if number not in seen:
            seen.add(number)
            result.append(number)
    return result

seen은 이미 나온 숫자인지 확인하고, result는 처음 나온 숫자를 순서대로 담는다. 집합 조회와 추가가 평균 O(1)이므로 전체 시간은 평균 O(n), 추가 공간은 O(n)이다.

딕셔너리 키로 정리하기

마지막에는 두 자료구조를 직접 관리하는 대신 dict.fromkeys()를 사용했다.

def unique_numbers(numbers):
    return list(dict.fromkeys(numbers))

assert unique_numbers([3, 1, 3, 2, 1]) == [3, 1, 2]
assert unique_numbers([]) == []

딕셔너리의 키는 중복되지 않으며, Python 3.7 이상에서는 삽입 순서가 보장된다. 따라서 입력으로 키를 만들고 그 키를 리스트로 변환하면 각 숫자가 처음 등장한 순서가 남는다. 추가한 assert 두 개는 중복이 섞인 입력과 빈 입력에서 기대하는 결과를 코드에 명시한다.

이 방식도 평균 O(n) 시간과 O(n) 공간을 사용한다. 단, 직전의 집합 방식과 마찬가지로 입력 원소는 딕셔너리 키로 쓸 수 있도록 해시 가능해야 한다.