Python으로 배열에서 특정 요소 제거하기 (제자리 알고리즘)

문제 개요

배열 nums와 값 val이 주어졌을 때, 배열 내에 존재하는 해당 값의 모든 인스턴스를 제자리(in-place)에서 제거하고 새로운 길이를 반환하는 문제입니다.

예를 들어, 입력이 [0,1,5,5,3,0,4,5], 5라면 값 5를 모두 제거한 후 남은 요소의 개수인 5가 출력됩니다.

해결 접근 방법

이 문제는 투 포인터(Two Pointer) 기법을 활용해 효율적으로 해결할 수 있습니다. 추가적인 배열을 만들지 않고 기존 배열 내에서 값을 덮어쓰는 방식입니다.

단계별로 살펴보면 다음과 같습니다.

카운터 변수 count를 0으로 초기화합니다. 이 변수는 제거 후 남은 요소의 위치(새 길이)를 가리킵니다.
배열의 각 인덱스 i를 순회하며 다음을 확인합니다.
- 만약 nums[i]가 val과 같지 않다면, 해당 값을 nums[count] 위치로 복사합니다.
- 그리고 count를 1 증가시킵니다.
순회가 끝나면 count를 반환합니다. 이 값이 곧 제거 후 배열의 새로운 길이입니다.

구현 예제

아래 코드를 통해 동작 방식을 더 쉽게 이해할 수 있습니다.

class Solution:
    def removeElement(self, nums, val):
        count = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[count] = nums[i]
                count += 1
        return count

ob = Solution()
print(ob.removeElement([0,1,5,5,3,0,4,5], 5))

입력

[0,1,5,5,3,0,4,5], 5

출력

동작 원리 설명

위 코드가 실행되는 과정을 단계별로 보면 다음과 같습니다.

1단계: count = 0으로 초기화합니다.
2단계: 배열을 처음부터 끝까지 순회하면서, 현재 요소가 삭제 대상 값(val = 5)이 아니면 배열 앞쪽의 count 위치에 덮어씁니다.
3단계: 결과적으로 값 5는 자연스럽게 배열 앞부분에서 밀려나며, 유효한 요소들은 배열의 앞쪽에 모이게 됩니다.
4단계: 최종적으로 count 값인 5가 반환됩니다. 이는 남아 있는 유효 요소의 개수입니다.

시간 및 공간 복잡도

시간 복잡도: O(n) — 배열을 한 번만 순회하면 되기 때문입니다.
공간 복잡도: O(1) — 추가 메모리 없이 기존 배열 내에서 처리하는 제자리(in-place) 알고리즘입니다.

이 방식은 코딩 테스트나 알고리즘 면접에서 자주 등장하는 유형으로, 배열을 직접 수정해야 하는 제약 조건이 있을 때 특히 유용하게 활용됩니다.