[PS-Blogself 테스트] 등장 순서를 유지하며 정수 리스트 중복 제거하기

중복을 제거하면서 처음 등장한 순서를 유지하려면, 이미 본 값인지 확인하는 일과 결과의 순서를 보관하는 일을 함께 처리해야 한다. 예를 들어 [3, 1, 3, 2, 1]에서는 처음 나온 값만 남겨 [3, 1, 2]를 만들어야 한다.

결과 리스트를 직접 탐색하면

처음에는 각 값이 결과 리스트에 없는 경우에만 추가했다. 입력을 앞에서부터 순회하므로 처음 등장한 순서는 자연스럽게 유지된다. 빈 입력도 그대로 빈 리스트가 된다.

다만 value not in result는 결과 리스트를 순차 탐색한다. 원소가 모두 다르면 확인할 리스트가 계속 길어지므로 전체 시간 복잡도는 O(n²)이다.

집합으로 확인하고 리스트에 순서대로 담기

중복 확인은 집합에 맡기고, 결과는 리스트에 담도록 바꾸었다. 집합에는 이미 등장한 값을 기록하고, 처음 본 값만 결과에 추가한다.

def unique_values(values):
    seen = set()
    result = []
    for value in values:
        if value not in seen:
            seen.add(value)
            result.append(value)
    return result

set(values)만 사용해도 중복은 제거되지만, 처음 등장한 순서는 보장되지 않는다. 이 함수는 집합을 조회용으로만 사용하고 입력을 순서대로 순회하며 결과 리스트를 만든다. 따라서 반복된 값은 첫 등장 때 한 번만 추가된다.

집합 조회와 추가는 평균 O(1)이므로 전체 시간 복잡도는 평균 O(n)이다. 집합과 결과 리스트에 값을 저장하므로 추가 공간은 O(n)이다. 빈 입력에서는 반복문을 건너뛰고 빈 리스트를 반환한다.

확인 체크리스트

• 빈 리스트를 넣으면 빈 리스트가 반환되는가?
• 중복된 정수가 한 번만 남는가?
• 결과가 처음 등장한 순서를 따르는가?