[문제] Remove Element

리트코드에서 문제를 풀어보았다! (lit코드 아니고 leet코드)

문제는 아래와 같다.

Given an array nums and a value val, remove all instances of the val in-place and return the new length.

nums라는 배열과 val이 주어질 때 val에 해당하는 원소를 모두 삭제하라는 아주 간단한 문제다.

예를 들어,

nums = [3,2,2,3] 
val = 3

# 결과로 3이 지워진 nums의 길이 2를 리턴해야 한다.

그러나 우리는 여기에서 remove in-place 에 주목해야한다.
위키피디아에 의하면..

In computer science, an in-place-algorithm is an algorithm which transforms input using no auxiliary data structure.

해석하자면 인풋을 추가(보조)적인 자료구조 없이 변경 하는 것을 의미한다.

However, a small amount tof extra storage space is allowed for auxiliary variables. The input is usually overwritten by the output as the algorithm executes. In-place algorithm updates input sequence only through replacement or swapping of elements. An algorithm which is not in-place is sometimes called not-in-place or out-of-place.

in-place 알고리즘은 원소끼리 순서를 뒤바꾸거나 교체하는 것으로 인풋을 업데이트한다!

그래서 in-place로 푼 문제는 아래와 같다.

def removeElement(self, nums: List[int], val: int) -> int:
	# 초기화
        start, end = 0, len(nums) - 1
        
        while start <= end:
            if nums[start] == val: 
                nums[start], nums[end], end = nums[end], nums[start], end - 1
            else: 
                start +=1
                
        return start

만일 생각나는대로 풀었다면 리스트 컴프리헨션이나 filter를 사용해서 문제를 풀었을텐데, 그러면 새로운 리스트를 만들어서 원하는 조건에 맞는 원소들을 복사 붙여넣기 하는 방식이 되기 때문에 in-place 라는 조건에 맞지 않게 된다.

해당 코드에서는 원하지 않는 조건(val과 같은)의 원소를 만났을 때 맨 뒤의 원소와 위치를 바꾸고 맨뒤를 가리키는 'end' 인덱스를 한칸 당겨옴으로서 삭제하는 것과 같은 효과를 내었다. 따라서 in-place, 즉 새로운 리스트 등의 자료구조를 만들지 않고도 주어진 자료구조 내부에서 원소들을 수정할 수 있게 되었다.

오늘은 in-place algorithm 의 조건에 대해 알아보았다! 끝!