배열 문제를 풀다 보면 중복을 제거하라는 문제는 자주 나옵니다.

그런데 이때 단순히 중복만 없애는 것이 아니라, 처음 등장한 순서를 그대로 유지하라는 조건이 붙으면 생각보다 헷갈릴 수 있습니다.

이번 글에서는 정수 배열에서 중복된 값을 제거하되, 원래 등장한 순서를 유지하는 문제를 정리해보겠습니다.

이 문제는 어렵지는 않지만, 배열 순회와 Set을 함께 쓰는 연습을 하기에 좋습니다.

문제

정수 배열 nums가 주어집니다.

이 배열에서 중복된 숫자는 제거하되, 처음 등장한 순서는 그대로 유지한 새 배열을 반환하는 함수를 작성해보겠습니다.

즉, 어떤 숫자가 여러 번 나오더라도 가장 처음 나온 한 번만 결과에 남기면 됩니다.

함수 형식은 아래와 같습니다.

remove_duplicates_keep_order(nums)
  • nums: 정수 배열
  • 반환값: 중복을 제거한 새 배열

예시 1

입력: [4, 2, 4, 3, 2, 1]
출력: [4, 2, 3, 1]

설명:

  • 첫 번째 4는 남깁니다
  • 첫 번째 2도 남깁니다
  • 뒤에 다시 나온 4, 2는 이미 본 숫자이므로 제거합니다
  • 3, 1은 처음 등장했으므로 결과에 추가합니다

예시 2

입력: [7, 7, 7, 7]
출력: [7]

설명:

  • 같은 숫자가 반복되므로 첫 번째 7만 남깁니다

예시 3

입력: [1, 3, 5, 7]
출력: [1, 3, 5, 7]

설명:

  • 중복이 없으므로 그대로 반환합니다

처음 떠오르는 생각

이 문제의 핵심은 두 가지입니다.

  1. 중복인지 확인해야 합니다
  2. 순서는 그대로 유지해야 합니다

여기서 많이 하는 실수가 정렬해서 중복을 제거하려는 것입니다.

예를 들어:

[4, 2, 4, 3, 2, 1]

이 배열을 정렬하면:

[1, 2, 2, 3, 4, 4]

이렇게 되어버립니다.

그러면 원래의 순서인 [4, 2, 3, 1]을 만들 수 없습니다.

즉, 이 문제는 정렬하면 안 되고, 앞에서부터 순서대로 보면서 처리해야 합니다.

핵심 아이디어

이 문제는 숫자를 하나씩 보면서 이미 본 숫자인지 빠르게 확인하면 됩니다.

이럴 때 Set이 잘 맞습니다.

  • 처음 보는 숫자면 Set에 넣고 결과 배열에도 추가합니다
  • 이미 본 숫자면 그냥 건너뜁니다

예를 들어 [4, 2, 4, 3, 2, 1]을 보면:

초기 상태는 아래와 같습니다.

seen = {}
result = []

이제 왼쪽부터 하나씩 확인합니다.

  • 4 → 처음 봄 → seen에 추가, result에 추가
  • 2 → 처음 봄 → 추가
  • 4 → 이미 봄 → 건너뜀
  • 3 → 처음 봄 → 추가
  • 2 → 이미 봄 → 건너뜀
  • 1 → 처음 봄 → 추가

최종 결과는 아래와 같습니다.

[4, 2, 3, 1]

코드

def remove_duplicates_keep_order(nums):
    seen = set()
    result = []

    for num in nums:
        if num not in seen:
            seen.add(num)
            result.append(num)

    return result

코드 해설

1) 이미 본 숫자를 저장할 공간 만들기

seen = set()

seen에는 지금까지 등장한 숫자를 저장합니다.

2) 결과 배열 만들기

result = []

중복이 제거된 최종 결과를 담을 리스트입니다.

3) 배열을 앞에서부터 확인하기

for num in nums:

순서를 유지해야 하므로 반드시 앞에서부터 차례대로 확인해야 합니다.

4) 처음 보는 숫자만 결과에 넣기

if num not in seen:
    seen.add(num)
    result.append(num)

이 부분이 핵심입니다.

  • seen에 없으면 처음 보는 숫자입니다
  • 그러면 seen에 기록하고
  • result에도 추가합니다

이미 본 숫자라면 아무것도 하지 않고 넘어갑니다.

실행 예시

입력:

[4, 2, 4, 3, 2, 1]

초기 상태:

seen = {}
result = []

4

  • 처음 봄
  • seen = {4}
  • result = [4]

2

  • 처음 봄
  • seen = {4, 2}
  • result = [4, 2]

4

  • 이미 봄
  • 그대로 넘어감

3

  • 처음 봄
  • seen = {4, 2, 3}
  • result = [4, 2, 3]

2

  • 이미 봄
  • 그대로 넘어감

1

  • 처음 봄
  • seen = {4, 2, 3, 1}
  • result = [4, 2, 3, 1]

최종 결과는 아래와 같습니다.

[4, 2, 3, 1]

복잡도

배열 길이를 N이라고 하면:

  • 시간 복잡도: O(N)
  • 공간 복잡도: O(N)

배열을 한 번만 순회하므로 시간은 O(N)입니다.

정리

이 문제는 단순 중복 제거와는 조금 다릅니다.

핵심은 순서를 유지해야 한다는 점입니다.

즉:

  • 정렬해서 풀면 안 됩니다
  • 앞에서부터 순회해야 합니다
  • 이미 본 값만 빠르게 체크하면 됩니다

이 문제의 핵심은 한 줄입니다.

배열을 앞에서부터 보면서, 처음 본 숫자만 결과에 추가합니다.

즉:

  • 순서대로 확인하고
  • 본 적 있는지 저장하고
  • 처음 나온 값만 남깁니다

이 흐름만 이해하면 쉽게 풀 수 있습니다.

이 글의 문제 상황과 예시는 학습용으로 직접 재구성한 내용입니다.