[코딩테스트 기초 07] 처음 나온 순서를 유지하며 중복 제거하기

정수 리스트에서 중복을 제거하되, 각 값이 처음 등장한 순서는 유지하는 문제입니다. 빈 입력은 빈 리스트를 반환하고 원본은 변경하지 않겠습니다.

[3, 1, 3, 2, 1] → [3, 1, 2]

sorted(set(numbers))는 중복을 제거하지만 결과를 크기순으로 바꿉니다. 이 문제에서 필요한 것은 정렬된 순서가 아니라 처음 등장한 순서예요.

확인용 집합과 결과 리스트를 나눕니다

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

print(unique_in_order([3, 1, 3, 2, 1]))
print(unique_in_order([]))
print(unique_in_order([0, -1, 0, -1, 2]))

[3, 1, 2]
[]
[0, -1, 2]

seen은 이미 처리한 값을 확인하고, result는 출력 순서를 보존합니다. 집합을 순회해서 결과를 만드는 것이 아니라 입력 리스트를 순서대로 읽으므로 첫 등장 순서가 유지됩니다.

두 자료구조의 역할이 다릅니다

앞에서 k개를 처리한 시점에 seen은 그 구간의 서로 다른 값을 담고, result는 각 값의 첫 등장 순서를 담습니다. 다음 값이 처음이면 두 곳에 추가하고, 이미 있다면 그대로 유지하면 됩니다.

결과를 집합으로만 비교하면 부족해요

assert unique_in_order([]) == []
assert unique_in_order([5, 5, 5]) == [5]
assert unique_in_order([3, 2, 1]) == [3, 2, 1]
assert unique_in_order([0, -1, 0]) == [0, -1]

numbers = [3, 1, 3, 2, 1]
before = numbers.copy()
assert unique_in_order(numbers) == [3, 1, 2]
assert numbers == before

set(result)만 비교하면 [1, 2, 3]도 통과할 수 있습니다. 순서까지 요구되는 문제이므로 기대 리스트와 직접 비교해야 합니다.

복잡도와 적용 범위

입력 길이가 n, 서로 다른 값의 수가 k일 때 집합 연산을 평균 O(1)로 보면 전체 평균 시간은 O(n), 집합과 결과를 저장하는 공간은 O(k)입니다. 결과 리스트에서만 number not in result를 검사하면 매번 선형 탐색이 필요해 최악 O(n²)이 될 수 있어요.

이 코드는 정수 입력을 전제로 합니다. 리스트처럼 해시할 수 없는 객체를 그대로 집합에 넣으면 오류가 납니다. 입력 범위가 달라지면 중복 판단 기준도 다시 정해야 합니다.

함께 보기

• 딕셔너리로 빈도표 만들기
• Python 공식 문서 — 집합