[leetcode] 27. Remove element

- 이전 블로그에서 2020. 7. 3.  에 본인이 직접 작성한 포스트를 옮겨온 글입니다.

출처: https://june13.tistory.com/10?category=873278 [Made for More]

 

1. 문제분석

https://leetcode.com/problems/remove-element/description/

Remove Element - LeetCode

난이도 : easy

 

 

간단히 nums 라는 array와 val이라는 값이 주어질텐데 , nums에서 val과 같은 원소들을 지우고 남은 array의 길이를 반환하는 문제이다. 영어로 읽었을때는 잘 안와닿았는데 예시를 보면 바로 무슨 말인지 알 수 있었다.

중요한 점은 따로 메모리를 할당하지 말고 input array 수정 하라고 되어있다.

 

포인트 

- 추가 array를 쓸 수 없다.
-  iter through nums  - val과 같은지 확인해야하니까 num의 모든 원소를 순회해야한다.

2. 풀이

 

- 2개의 idx를 가지고 순회하면 될것 같다. (idx1 = read index / idx2 =write idx )

- 처음엔 같이시작해서 만일 읽은 값이 val이면 write 하지않는다(해당 index에 머문다,)

 

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        idx2=0;
        for idx1 in range(len(nums)):
        # if val in place idx1++
            if nums[idx1]==val:
                continue
        # if val not in place write idx2 on idx1 idx1++ idx2++
            else:
                nums[idx2]=nums[idx1]
                idx2=idx2+1
        nums=nums[:idx2]
        return len(nums)
            

 
Time complexity : O(n)  -> nums의 길이가 n 일때 i와 j는 최대 2n 번 움직인다. (val값이 하나도 없을 때)
Space complexity :  O(1)   문제의 기본 요구조건이었다.
 
 

3. 다른 풀이

 

영어로는 Two pointers 라고 표현되어 있었다.

"This is a pretty easy problem" 

 

approach 1 : 아래는 java로 작성된 솔루션

public int removeElement(int[] nums, int val) {
    int i = 0;
    for (int j = 0; j < nums.length; j++) {
        if (nums[j] != val) {
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
}

음.. 이걸보니 왜 난 굳이 == 와 continue를 썼나 싶다. !=로 하면 else도 쓸일이 없었구나... 

앗! 그리고 len을 굳이 return 할 필요도 없었다. 실제 배열의 순서가 중요하지 않다고 했던게 힌트였다고 한다. 

 

이렇게 다시 python으로 풀이를 작성해봤다.

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:    
        idx2=0;
        for idx1 in range(len(nums)):
            if nums[idx1]!=val:
                nums[idx2]=nums[idx1]
                idx2=idx2+1
        return idx2

 

Runtime: 32 ms

Memory Usage: 14 MB

->

Runtime: 28 ms

Memory Usage: 13.9 MB

 

속도가 아주 조금 개선되었다,ㅎㅎ

 

approach 2  : 

" when elements to remove are rare"  즉, 지울게 별로 없는 상황에 특화된,.?

 

public int removeElement(int[] nums, int val) {
    int i = 0;
    int n = nums.length;
    while (i < n) {
        if (nums[i] == val) {
            nums[i] = nums[n - 1];
            // reduce array size by one
            n--;
        } else {
            i++;
        }
    }
    return n;
}

안지우는애들은 그냥 지나가고 지우는 동작 대신 맨뒤 원소를 가져온다.

 

 

Time complexity : O(n)O(n). Both ii and nn traverse at most nn steps. In this approach, the number of assignment operations is equal to the number of elements to remove. So it is more efficient if elements to remove are rare.

 

 앞 알고리즘대로는 한번이라도 idx1와 idx2가 어긋나면 계속 대입을 다시 하게되는데 이 알고리즘은 딱 지우는 개수 만큼만 대입연산을 하게된다.! list의 순서가 바뀌어도 된다는 점을 적극적으로 이용했다고 볼 수 있다. 

 

 

4. 후기 

 아주 단순한 문제였기 때문에 깊은고찰 없이도 쉽게 풀수 있었다. 문제의 조건들을 꼼꼼히 살펴서 이를 최대한 활용한 솔루션이 인상적이었다. 문제의 작은 조건이라도 그냥 지나치지 않는 자세가 앞으로 어려운 문제로 갈수록 중요할 것 같다.