Remove Element

안녕하세요, 오늘은 Leet Code의 27번 문제를 풀어보겠습니다.

 

문제 링크

문제 내용
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val. Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
• Return k.

Example 1:
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

 

문제 접근

코딩테스트 문제는 쉽게 접근하는게 좋다.

우리 머리 속에는 nums 리스트에서 val을 제거하고 반환하면 되겠지 생각할 것이다.

 

 

문제 풀이

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

 

그러나 여기서 우리는 놓치지 말아야 할 것이 있다.

• 앞에서부터 한개씩 지우는 순차 처리 과정에 과연 문제가 없을까?

 

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        while val in nums: # 값이 있는동안 무한루프
            nums.remove(val)

• while문으로 값이 있는 동안에는 무한루프를 돌게하고 제거하면 되겠다.
  => 그런데 생각을 해보면, 리스트의 값을 하나 제거하고 전체 길이에서 val가 있나 확인하고 또 하나를 제거하고 확인하고 반복하면 비효율 적일 것 같다는 느낌이 들어야 한다.

첫번째 결과 (비 효율적인 코드)

모든 Test Case를 통과하긴 했지만, 나의 코드는 상당히 느리고 비효율 적인 것으로 나온다.

 

 

문제 해결

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        memo = []
        for i in range(len(nums)):
            if nums[i] == val:
                memo.append(i)
        memo.sort(reverse = True)
        for i in memo:
            del nums[i]

 

다음과 같이 풀면 어떨지 생각해보자

• val과 일치하는 index를 기록한다.
• 각 인덱스 기준으로 nums를 앞에서부터 지우면 원소 한개씩 당겨지기 때문에 지우는데 오류가 발생한다.
  (이래서 실무에서는 원본은 건드리면 위험성이 따른다는 것을 알았으면 한다)
• 그러면 뒤에서부터 지워야하는데 전략은 reverse를 쓰는 방법이다.

두번째 결과(효율적인 코드 완성!!)

위와같이 훨씬 효율적이고 빨라졌음을 알 수 있다.

 

 

오늘도 재미있는 하루를 보낸 기분~

끝!