LeetCode 27(Remove Element, Python)

1. 문제 링크 

Remove Element - LeetCode

Remove Element - LeetCode

 

2. 문제 설명

• int가 담긴 리스트 nums와 int인 val이 주어졌을 때, nums에서 val은 모두 제외하고 남은 개수를 반환한다. val을 제외한 개수가 k개라면 리스트의 앞쪽 k개에는 val이 없어야한다. 즉 삭제되거나 뒤쪽으로 밀어 두어야한다.
• 예시) nums = [3, 2, 2, 3]과 val =3 이 주어지면 3을 제외하고 nums = [2, 2] 또는 [2, 2, _, _]을 반환(_은 무엇이든 상관 없음)
• 그런데 이를 in-place 알고리즘으로 구현해야 한다. 이에 대한 자세한 내용은 5번 배운 점에 쓰고, 간단히 말해 nums를 어딘가에 복사하는 것처럼 nums 크기에 비례하는 추가 공간을 사용하지 말라는 뜻이다. 

3. 처음 풀이

• del은 추가 공간 없이 주어진 리스트를 변경할 수 있음
• 인덱스 i=0으로 설정하고 i번째 원소가 주어진 val과 같으면 del nums[i]하여 삭제
• i를 1씩 키우며 마지막까지 while문 반복

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i=0

        while i!=len(nums): #i가 nums 끝까지 갈 때까지 반복
            if nums[i]==val: #i번째 원소가 val과 같으면 삭제
                del nums[i]
            else: 
                i+=1 #그렇지 않으면 다음 i로 이동
        return len(nums) #완료 후 nums 길이 반환

 

4. 개선된 풀이

• del 은 인덱스 기준으로 삭제할 수 있고 remove를 하면 값 기준으로 삭제 가능

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        while val in nums:
            nums.remove(val)

5. 배운점

• in-place 알고리즘(위키피디아: 현재 위치 알고리즘 - 위키백과, 우리 모두의 백과사전 (wikipedia.org) )
• In-place 알고리즘은 추가적인 메모리 공간을 사용하지 않고 주어진 입력 데이터를 직접 수정하거나 재배열하는 알고리즘
• 리스트 배열을 뒤집을 때 in-place 알고리즘과 그렇지 않은 알고리즘의 예시

#In-Place 알고리즘 예시
#추가 메모리를 사용하지 않고 주어진 리스트를 직접 변경
def reverse_in_place(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

my_list = [1, 2, 3, 4, 5]
reverse_in_place(my_list)
print(my_list)  # [5, 4, 3, 2, 1]

#비-In-Place 알고리즘 예시
#원본 리스트를 변경하지 않고 새로운 역순으로 된 리스트를 반환, 추가 메모리를 사용하여 새로운 리스트를 생성
def reverse_not_in_place(arr):
    reversed_arr = arr[::-1]
    return reversed_arr

my_list = [1, 2, 3, 4, 5]
new_list = reverse_not_in_place(my_list)
print(my_list)  # [1, 2, 3, 4, 5]
print(new_list)  # [5, 4, 3, 2, 1]

• 장점
  • 메모리 효율성
  • 시간 효율성
• 단점
  • 원본 데이터 변경으로 데이터 손실 위험
• del VS remove
  • del list[i] 하면 인덱스 기준 삭제
  • list.remove(val) 하면 값 기준 삭제