(Array / String) Remove Element

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

1안

in-place라고 해서 처음에 아래와 같이 풀었다.
val과 같으면 스왑 - 모두 스왑한 이후 뒤부터 탐색하면서 val과 동일 원소 갯수 세기
스왑하기 위해 탐색하고 있으므로 최악의 경우 시간복잡도는 O(n^2)
최적화 필요할 듯.

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

        int k = 0;
        for (int i=nums.length-1; i>=0; i--) {
            if (nums[i] == val) k++;
        }
        
        return nums.length - k;
    }
}

2안 - 최적화

솔루션 참고함.
별도 인덱스를 따로 구성해서 덮어씌우는 방식.
nums[i]가 val이 아닌 경우 인덱스++ 하면서 덮어씌우면 결국에는 k번째까지는 유효한 수들만 남음.
문제 풀이를 위해 원본 배열 전부를 특정 기준으로 정렬할 필요가 없는것

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];
            }
        }
        return k;    
    }
}