[Leetcode] 27. Remove Element - JS

https://leetcode.com/problems/remove-element/description/?envType=study-plan-v2&envId=top-interview-150

 

 

1. 문제 분석

문제분석
----------------------------
정수배열 nums와 정수 val이 주어진다.
nums 배열 속 제자리에 있는 val을 모두 제거하라.
nums 배열의 순서는 변경될 수 있다.
nums 배열에서 val과 다른 요소의 갯수(k)를 반환하라.

제한조건
----------------------------
- 0 <= nums.length <= 100
- 0 <= nums[i] <= 50
- 0 <= val <= 100

예시
----------------------------
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]

- 예시로 결과값의 nums에 '_'를 추가했지만 어떤 값이 들어가도 상관 없다.

 

 

2. 접근 방법

포인터를 활용
1. 첫번째 순회 때, val과 같은 값은 '_'로 수정하면서 k 구함
2. 두번째 순회 때, 포인터를 지정
    - 포인터에 해당하는 요소 값과 순회하는 값을 확인하여 
    - 포인터에 해당하는 값이 '_'이고 순회하는 값이 '_'가 아니면 swap
    - 포인터 이동

 

 

풀이

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    let k = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === val) {
            nums[i] = '_'
        } else {
            k++;
        }
    }

    let pointer = 0;
    for (let i = 1; i < nums.length; i++) {
        if (nums[pointer] !== '_') {
            pointer++;
            continue;
        };
        if (nums[i] !== '_') {
            swap(nums,pointer,i);
            pointer++;
        }
    }

    return k;
};

function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]]
}

 

위 풀이의 복잡도 분석은 다음과 같다.

 

- 시간복잡도: O(n)

- 공간복잡도: O(1)

 

다른 사람 풀이

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
    	if (nums[i] !== val) {
            nums[count++] = nums[i]
        }
    }
    return count;
};

내가 푼 풀이는 첫번째 순회 때 val과 같은 요소를 '_'로 변경해주고 같지 않을 때 k를 구한 뒤,

두번째 순회 때 '_'인지 아닌지 판단하는 로직을 추가하면서 가독성이 떨어졌다.

 

하지만 위 풀이는 val과 같지 않은 요소의 갯수와 이동할 인덱스를 하나로 통합하여 코드가 훨씬 간결하고 이해하기 편하다.

즉, count가 포인터 역할을 같이 해주는 풀이 방법이다.