[two pointer] 릿코드 27. Remove Element

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

Remove Element - LeetCode

 

첫번째 방법(성공)

문제에서 in-place, 순서는 변경해도 된다고 한다
=> 포인터가 뒤에서 앞으로 이동 가능

투포인터 left, right

left 는 "대체 당해야하는 인덱스"로 val를 찾을 때까지 왼쪽에서 오른쪽으로 이동

right은 "대체해야하는 인덱스"로  val 이외를 찾을 때까지 오른쪽에서 왼쪽으로 이동

 

left, right 둘 다 찾으면 nums[left] = nums[right]으로 replace하고 left++, right-- 이동한다.

이를 left > right할 때까지 반복한다

var removeElement = function(nums, val) {
    let left = 0;
    let right = nums.length-1;
    
    while(left <= right) {
        // 교체당할 곳과 교체할 곳을 모두 찾으면 교체한다
        if (nums[left] === val && nums[right] !== val) {
            nums[left] = nums[right];
            left++; // 교체 후 이동
            right--;
        } else {
            if (nums[left] !== val) {
                left++;
            }
            if (nums[right] === val) {
                right--;
            }
        }
    }
    return right+1; 
};

 

두번째 방법(성공)

투 포인터 i, num은 앞에서 뒤로 이동한다

i는 val 값인 곳으로 "대체 당해야하는 인덱스"

num은 val 이외의 값인 "대체해야하는 인덱스"이다

 

이 두 포인터는 nums를 반복문 안에서 앞에서 뒤로 이동하는데

단 현재num이 val이면 i는 멈춘다 

이는 num의 값이 val이 아닐떄까지 반복되며, val이 아닌 값을 찾으면 i위치의 값을 현재 num으로 대체한다.

 

이렇게 nums 반복을 다 돌고 나면 i 전 까지는 val이 아닌 값들이다

var removeElement = function(nums, val) {
    let i = 0;
    for (const num of nums) {
        // val가 아닌 수를 찾으면
        if (num !== val) {
            nums[i] = num; // i위치를 val가 아닌 수로 replace한다 (자기자신이 val가 아니면 자기자신이 replace)
            i++;
        }
    }
    return i;
};

 

차이점

첫번째 방법은 속도가 빠르지만 배열의 순서가 바뀐다

두번째 방법은 속도는 느리지만 배열의 순서가 유지된다

 

느낀점

개인적으로 첫번째 코드보다 두번째가 이해하기에는 더 간결한 로직이라고 생각한다.

하지만 두번째는 아직은 경험이 더 쌓여야 빨리 생각해낼 수 있을 것 같다.

어느 것이 맞다 틀리다가아니라 상황에 따라서 다른 방법을 찾는게 재밌었다.