[LEETCODE 150] - 27 Remove Element

 

LeetCode 27번 문제는 정수 배열 nums와 특정값 val이 주어졌을때 배열 내에서 val과 일치하는 모든 요소를 제자리(In-place)에서 삭제하는 알고리즘을 설계하는 문제다.이 문제는 추가적인 배열 공간을 할당하지 않고 기존 배열을 수정해야 하며, 수정 후 val이 아닌 요소들의 개수를 반환해야 한다.배열 앞부분에는 val이 제거된 요소들이 남게 되며, 그 뒤의 순서나 남은 값들은 결과에 영향을 주지 않는다.

 

Key Findings

 

두 개의 포인터: 읽기 포인터와 쓰기 포인터를 사용하는 '투 포인터(Two Pointers)' 기법이 가장 효율적인 해결책입니다.

반환 값: val과 일치하지 않는 요소의 총 개수 k를 반환하며, 배열의 앞쪽 k개의 요소는 val이 아닌 값들로 채워져 있어야 합니다.

그림으로 문제를 그려봤다

 

알고리즘 작동 원리 (투 포인터)

 

이 문제는 배열을 순차적으로 탐색하면서, 우리가 유지하고 싶은 값(즉, val이 아닌값)만 배열의 앞쪽으로 차곡차곡 쌓아나가는 방식으로 해결한다.

 

1. 포인터 설정: k 라는 변수를 0으로 설정합니다. 이 k는 val이 아닌 값이 들어갈 위치를 가리키는 '쓰기 포인터' 역할을 합니다.

2. 배열 순회: for 루프를 사용하여 배열의 각 요소 nums[i] 를 확인합니다.

3. 조건 확인: 만약 nums[i] 가 제거해야 할 값인 val과 다르다면:

• nums[k] 위치에 현재 값 nums[i]를 저장합니다
• k 값을 1 증가시켜 다음 저장 위치를 준비합니다.

4.결과 반환: 모든 순회가 끝나면 k에는 val이 아닌 요소의 개수가 저장되어 있으며, 이를 반환합니다.

 

정답 코드 (Python)

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

 

 

시간 복잡도: 배열을 한 번만 순회하면 되므로 O(n)의 시간 복잡도를 가집니다.