[Array/String] Remove Element

1. 문제

LeetCode - Remove Element
정수 배열 nums와 정수 val이 주어졌을 때, nums에서 val이 포함된 모든 항목을 제자리에서 제거하고, nums에서 val과 같지 않은 요소의 수를 반환하는 문제

2. 접근법

1. 처음에는 배열 nums에서 val과 같지 않은 요소를 전부 -1로 변환하는 방법으로 접근 → 테스트 통과 X
2. nums에서 val과 같지 않은 요소들을 nums안에서 재배치 해줘야 테스트를 통과할 수 있는것으로 파악
3. 이후 ArrayList를 활용 → val과 같지 않은 요소들을 전부 추가
4. k에는 val과 같지 않은 요소들의 수를 할당
5. ArrayList에 담긴 요소들을 nums 앞에서부터 재배치시켜 테스트 통과

3. 풀이

import java.util.ArrayList;

class Solution {
    public int removeElement(int[] nums, int val) {
        // val과 같지 않은 요소의 수 k
        int k = 0;

        // val과 다른 요소를 담기 위해 ArrayList 활용
        ArrayList<Integer> list = new ArrayList<>();

        // k수 세기 & ArrayList에 담기
        for (int n : nums) {
            if (n != val) {
                k++;
                list.add(n);
            }
        }

        // nums 재배치
        for (int i = 0; i < list.size(); i++) {
            nums[i] = list.get(i);
        }

        return k;
    }
}

4. 성능

- Runtime : 0ms

- Memory : 41.1mb

5. 개선

• 문제에서 in-place(제자리)에서 제거할 것을 요구했기 때문에 개선 방법이 더 문제의 요구사항에 부합하는 방법이라고 생각했다.
• 별도의 ArrayList를 활용할 필요 없이 k를 인덱스로 활용하는 방법(two-pointer 접근법)
• k를 인덱스로 활용함으로써 간단하게 nums를 앞에서부터 재배치할 수 있었다.

class Solution {
    public int removeElement(int[] nums, int val) {
        int k = 0;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[k] = nums[i];
                k++;
            }
        }

        return k;
    }
}