기술면접 - 배열에서 중복 제거 (Remove Duplicates from Sorted Array)

문제 개요

정렬된 배열이 주어졌을 때, 중복된 요소를 제거하여 각 요소가 한 번씩만 나타나도록 하고 새로운 배열의 길이를 반환해야 합니다. 이 작업은 제자리(in-place) 알고리즘으로 수행해야 하며, 추가 메모리 사용은 O(1)로 제한됩니다.

제약 조건:

• 입력 배열은 오름차순으로 정렬되어 있습니다.
• 0 ≤ 배열 길이 ≤ 3 * 10⁴
• -100 ≤ 배열 요소 ≤ 100

예제:

입력: nums = [1,1,2]

출력: 2, nums = [1,2,_]

입력: nums = [0,0,1,1,1,2,2,3,3,4]

출력: 5, nums = [0,1,2,3,4,_,_,_,_,_]

C 언어 구현

아래는 정렬된 배열에서 중복을 제거하는 제자리 알고리즘의 C 언어 구현입니다.

#include 

int removeDuplicates(int* nums, int numsSize) {
    // 예외 처리
    if (numsSize == 0) return 0;
    
    // 고유 요소를 저장할 위치 포인터
    int writeIndex = 1;
    
    // 두 번째 요소부터 배열 순회
    for (int readIndex = 1; readIndex < numsSize; readIndex++) {
        // 현재 요소가 이전 요소와 다르면
        if (nums[readIndex] != nums[readIndex - 1]) {
            // writeIndex 위치에 복사
            nums[writeIndex] = nums[readIndex];
            writeIndex++;
        }
    }
    
    return writeIndex;
}

// 사용 예제
int main() {
    int nums[] = {0,0,1,1,1,2,2,3,3,4};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    
    int newLength = removeDuplicates(nums, numsSize);
    
    printf("새로운 길이: %d\n", newLength);
    printf("중복 제거 후 배열: ");
    for (int i = 0; i < newLength; i++) {
        printf("%d ", nums[i]);
    }
    printf("\n");
    
    return 0;
}

알고리즘 설명

이 알고리즘은 투 포인터 기법을 사용하여 배열을 제자리에서 수정합니다:

1. writeIndex: 다음 고유 요소가 저장될 위치를 가리킵니다.
2. readIndex: 배열을 순회하며 고유 요소를 찾습니다.

작동 방식:

1. 배열이 비어 있으면 0을 반환합니다.
2. writeIndex를 1로 초기화합니다(첫 번째 요소는 항상 고유).
3. readIndex를 1부터 배열 끝까지 순회합니다.
4. 각 요소를 이전 요소(nums[readIndex - 1])와 비교합니다.
5. 다르면 현재 요소를 nums[writeIndex]에 복사하고 writeIndex를 증가시킵니다.
6. writeIndex를 새로운 길이로 반환합니다.

writeIndex까지의 배열은 고유한 요소들로 구성되며, 나머지 부분은 무시됩니다.

시간 및 공간 복잡도

• 시간 복잡도: O(n)
  • readIndex로 배열을 한 번 순회합니다.
  • 각 요소는 한 번 비교되며, 최대 n개의 요소가 복사됩니다.
• 공간 복잡도: O(1)
• 제자리 수정으로 두 개의 포인터(writeIndex, readIndex)만 사용합니다.
• 추가 데이터 구조를 사용하지 않습니다.

이 접근법의 장점

이 솔루션은 다음과 같은 이유로 최적입니다:

• 제자리 수정 요구사항을 충족합니다.
• 최소한의 추가 공간(O(1))을 사용합니다.
• 정렬된 배열의 특성을 활용해 인접 요소만 비교하므로 불필요한 비교를 피합니다.
• 단일 순회로 간단하고 효율적입니다.

시각적 예제

nums = [0,0,1,1,1,2,2,3,3,4]를 예로 들어 과정을 살펴보겠습니다:

단계	readIndex	writeIndex	nums	작업
초기	-	1	[0,0,1,1,1,2,2,3,3,4]	-
1	1	1	[0,0,1,1,1,2,2,3,3,4]	0 == 0, 건너뛰기
2	2	1	[0,0,1,1,1,2,2,3,3,4]	1 != 0, nums[1] = 1, writeIndex++
3	3	2	[0,1,1,1,1,2,2,3,3,4]	1 == 1, 건너뛰기
4	4	2	[0,1,1,1,1,2,2,3,3,4]	1 == 1, 건너뛰기
5	5	2	[0,1,1,1,1,2,2,3,3,4]	2 != 1, nums[2] = 2, writeIndex++
최종	-	5	[0,1,2,3,4,2,2,3,3,4]	5 반환

출력: 길이 = 5, 배열 = [0,1,2,3,4]

결론

이 C 언어 구현은 투 포인터 기법을 사용하여 정렬된 배열에서 중복을 효율적으로 제거합니다. 제자리 수정과 O(1) 공간 복잡도를 유지하며, 간단하고 최적화된 솔루션입니다.