Remove Duplicates from Sorted Array

Q: 정렬된 배열에서 중복 항목 제거의 시간 복잡도는 얼마인가요?

쓰기 포인터 방식은 각 값을 한 번씩 읽으므로 O(n) 시간에 실행됩니다. 반환하는 값 외에 O(1) 의 추가 공간, 즉 인덱스 두 개를 사용합니다.

Q: 추가 메모리 없이 제자리에서 중복 항목을 제거하려면 어떻게 해야 하나요?

읽기 인덱스 옆에 쓰기 인덱스 k 를 둡니다. 처음 k 개의 슬롯에는 지금까지 확인한 고유한 값이 들어 있습니다. 읽은 값이 nums[k-1] 와 다르면 해당 값을 nums[k] 에 복사하고 k 를 증가시킵니다. 쓰기 인덱스는 읽기 인덱스를 절대 앞서지 않으므로, 값을 읽기 전에 덮어쓰는 일이 없습니다.

Q: 각 값이 최대 두 번씩만 허용되도록 하려면 어떻게 해야 할까요?

하나 앞이 아니라 유지된 부분에서 두 자리 앞의 값과 비교하세요. k < 2 이거나 nums[i] 가 nums[k-2] 와 다르면 nums[i] 를 복사하세요. nums[i] 가 nums[k-2] 와 같으면 유지된 부분의 끝에 이미 그 값이 두 개 있습니다. 같은 아이디어를 사용하면 nums[k-m] 을 통해 최대 m 개의 복사본을 허용할 수 있습니다.

쉬움투 포인터

+10

정수가 비내림차순으로 정렬된 배열 nums가 주어집니다. 따라서 같은 값은 서로 인접해 있습니다. nums의 고유한 값을 각각 한 번씩, 나타나는 순서대로 반환하세요. 예를 들어, [2, 2, 5]는 [2, 5]를 반환합니다.

함수

removeDuplicates(nums: integer-array) → integer-array

numsinteger-array: 정수, 비내림차순으로 정렬됨
반환값integer-array: nums의 서로 다른 값들을 오름차순으로

제약 조건

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
nums는 비감소 순으로 정렬되어 있습니다.

예제

입력: nums = [1, 1, 2, 3, 3, 3]
출력: [1, 2, 3]
설명: 1은 두 번, 3은 세 번 나타납니다. 각각 하나씩 남기면 [1, 2, 3]이 됩니다.

입력: nums = [-2, 0, 0, 5]
출력: [-2, 0, 5]
설명: 0만 반복됩니다. 음수 값도 같은 방식으로 작동하므로 답은 [-2, 0, 5]입니다.

입력: nums = [7, 7, 7]
출력: [7]
설명: 모든 값이 7이므로 7 하나만 남습니다.

제출 시 숨은 테스트 +15개

후속 질문

nums를 새 배열로 만들지 않고 제자리에서 다시 작성하여 추가 메모리 O(1)로 할 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

임의의 배열에서 중복 항목을 제거하려면 지금까지 본 모든 값을 기억해야 합니다. 정렬된 입력에서는 그럴 필요가 없습니다. 같은 값은 서로 이웃하므로, 값이 새 값인지 여부는 마지막으로 보관한 값과 다른지만 확인하면 됩니다. 따라서 추가 메모리 없이 두 개의 인덱스로 한 번만 순회하면 됩니다.

해시 집합에 이미 본 값을 기억하기

핵심 아이디어

nums를 순회하면서 답에 이미 추가한 값들을 집합에 저장합니다. 값이 집합에 없으면 답에 추가하고 집합에도 넣습니다. 집합에 있으면 건너뜁니다. [1, 1, 2, 3, 3, 3]의 경우 답은 [1]이 되고, 이어서 [1, 2], 그다음 [1, 2, 3]이 되며, 이후의 중복 값은 모두 건너뜁니다.

각 값은 처음 나타날 때 순서대로 한 번만 추가되므로 답이 올바릅니다. 이 방법은 nums가 정렬되어 있다는 점을 전혀 이용하지 않으므로 어떤 배열에도 적용할 수 있습니다.

집합 조회는 평균적으로 O(1)이므로 한 번 순회하는 데 O(n) 시간이 걸립니다. 하지만 집합과 답은 각각 최대 n개의 값을 담을 수 있어 추가 공간은 O(n)입니다. C에는 내장 집합이 없으므로 2 × 10^4 + 1개의 가능한 값을 표시하는 플래그 배열을 사용하면 같은 작업을 할 수 있습니다.

알고리즘

빈 집합 seen과 빈 리스트 result를 만듭니다.
nums의 각 값이 seen에 있는지 확인합니다.
없다면 seen에 추가하고 result에 덧붙입니다.
result를 반환합니다.

def removeDuplicates(nums):
    seen = set()
    result = []
    for num in nums:
        if num not in seen:
            seen.add(num)
            result.append(num)
    return result

쓰기 포인터를 사용해 제자리에서 압축하기

핵심 아이디어

정렬된 입력에서는 값의 모든 복사본이 하나의 연속 구간을 이루므로, 마지막으로 남겨 둔 값과 다를 때만 새로운 값입니다. 집합이 아니라 비교 한 번이면 충분합니다.

인덱스 두 개를 사용합니다. 읽기 인덱스 i는 모든 값을 방문합니다. 쓰기 인덱스 k는 남겨 둔 부분의 끝을 나타냅니다. 즉, nums[0]부터 nums[k-1]까지에는 지금까지 찾은 고유한 값이 항상 들어 있습니다. 첫 번째 값은 항상 남겨 두므로 k = 1로 시작합니다. nums[i]가 nums[k-1]과 다르면 해당 값을 nums[k]에 복사하고 k를 앞으로 이동합니다.

[1, 1, 2, 3, 3, 3]에서: i = 1은 두 번째 1을 읽으며 아무 일도 일어나지 않습니다. i = 2는 2를 읽는데, 이는 nums[0] = 1과 다르므로 인덱스 1에 들어가고 k는 2가 됩니다. i = 3은 3을 인덱스 2에 쓰고 k는 3이 됩니다. 마지막 두 3은 nums[2]와 일치하므로 건너뜁니다. 이제 처음 세 칸에는 [1, 2, 3]이 들어 있습니다.

쓰기 인덱스가 읽기 인덱스를 앞지르는 일은 없습니다. k는 항상 i보다 작거나 같기 때문에 값을 읽기 전에 덮어쓰지 않습니다. 한 번 순회하므로 시간 복잡도는 O(n)이며, 반환되는 값을 제외하면 정수 두 개만 사용하므로 추가 공간은 O(1)입니다.

알고리즘

k = 1로 설정합니다: nums[0]은 항상 유지됩니다.
i를 1부터 마지막 인덱스까지 반복합니다.
nums[i]가 nums[k-1]와 다르면 nums[k] = nums[i]로 설정하고 k에 1을 더합니다.
nums의 처음 k개 값을 반환합니다.

def removeDuplicates(nums):
    # nums[0:k] holds the distinct values found so far, in order.
    k = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[k - 1]:
            nums[k] = nums[i]
            k += 1
    return nums[:k]

함정과 경계 사례

쓰기 포인터는 짧고, 관련 버그는 어떤 값과 비교하느냐에 관한 것입니다.

i가 마지막 인덱스까지 실행되는 동안 nums[i]를 nums[i+1]과 비교하는 경우입니다. 마지막 비교에서 배열의 끝을 한 칸 넘어선 위치를 읽습니다.
k를 0에서 시작하는 경우입니다. 그러면 첫 번째 값을 nums[-1]과 비교하게 되는데, 이는 범위를 벗어나거나 Python에서는 마지막 요소를 가리킵니다.
배열 전체를 반환하고 처음 k개 값만 반환하지 않는 경우입니다. 뒤쪽에는 이전 값이 그대로 남아 있으므로 [1, 1, 2]는 [1, 2, 2]로 반환될 수 있습니다.
해시 집합을 순회해 답을 만드는 경우입니다. 대부분의 언어에서 해시 집합은 순서를 유지하지 않으므로 값이 뒤섞여 나올 수 있습니다. 대신 각 값을 처음 만났을 때 리스트에 추가하세요.
Lua와 R에서는 배열의 인덱스가 1부터 시작합니다. 유지할 부분은 nums[1]부터 nums[k]까지이며, 비교 대상은 nums[k-1]이 아니라 nums[k]입니다.

자주 묻는 질문4

정렬된 배열에서 중복 항목 제거의 시간 복잡도는 얼마인가요?

쓰기 포인터 방식은 각 값을 한 번씩 읽으므로 O(n) 시간에 실행됩니다. 반환하는 값 외에 O(1)의 추가 공간, 즉 인덱스 두 개를 사용합니다.

배열은 왜 정렬해야 하나요?

정렬하면 같은 값의 모든 복사본이 하나의 연속 구간에 모이므로, 값이 새 값인 경우는 보관한 마지막 값과 다를 때뿐입니다. 정렬되지 않은 배열에서는 복사본이 첫 번째 복사본에서 멀리 떨어진 곳에 나타날 수 있으며, 이미 본 모든 값을 기억하려면 해시 집합이 필요하고, 이 경우 O(n)의 추가 공간이 듭니다.

추가 메모리 없이 제자리에서 중복 항목을 제거하려면 어떻게 해야 하나요?

읽기 인덱스 옆에 쓰기 인덱스 k를 둡니다. 처음 k개의 슬롯에는 지금까지 확인한 고유한 값이 들어 있습니다. 읽은 값이 nums[k-1]와 다르면 해당 값을 nums[k]에 복사하고 k를 증가시킵니다. 쓰기 인덱스는 읽기 인덱스를 절대 앞서지 않으므로, 값을 읽기 전에 덮어쓰는 일이 없습니다.

각 값이 최대 두 번씩만 허용되도록 하려면 어떻게 해야 할까요?

하나 앞이 아니라 유지된 부분에서 두 자리 앞의 값과 비교하세요. k < 2이거나 nums[i]가 nums[k-2]와 다르면 nums[i]를 복사하세요. nums[i]가 nums[k-2]와 같으면 유지된 부분의 끝에 이미 그 값이 두 개 있습니다. 같은 아이디어를 사용하면 nums[k-m]을 통해 최대 m개의 복사본을 허용할 수 있습니다.

Python

def removeDuplicates(nums):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

nums = [1, 1, 2, 3, 3, 3]

기대값

[1, 2, 3]