문제

nums 배열에서 모든 val 값을 지우고 남은 원소의 개수(k)를 리턴한다. 이 때, nums 배열의 0 ~ k-1번째 인덱스는 지워지지 않고 남은 원소로 채워져야한다. 예를들어, nums = [0,1,2,2,3,0,4,2], val = 2일때 5를 리턴하고 nums 배열은 [0,1,3,0,4,x,x,x] 형태가 되어야한다.(배열 값의 검증은 0 ~ k-1번째 인덱스까지만 한다. 따라서 x값은 어떤 값이어도 상관없다.)

풀이

처음 생각한 알고리즘은 다음과 같다.

1. nums[i]의 원소가 val이면 nums[i] = -1 (-1은 원소가 지워져 빈자리라는 의미)
2. nums[i]의 원소가 val이 아니면
	2-1. i-1번째 인덱스부터 nums[i-k](k= 2~i)를 조회하며 빈 자리를 찾는다.
	2-2. 빈 자리를 찾으면 i번째 원소를 i-k번째에 넣고 i번째를 -1로 채운다.
3. 1~2번 과정을 i가 nums.length - 1이 될 때까지 반복한다.

하지만 $O(n^2)$의 시간복잡도를 갖게되어 효율적이지 않다는 생각을 했다. nums 배열에서 val에 해당하는 값들을 지우고 지워지지 않은 원소들을 빈 칸에 땡겨 채우는 방식을 떠올리려고 노력했다. 그 결과로 떠올린 방식은 누적합을 이용하는 것이었다.

누적합을 이용한 방식은 다음과 같다.

1. 누적합을 구하기 위해 nums와 길이가 같은 temp 배열을 생성한다.
2. nums 배열을 i ~ nums.length - 1까지 반복한다. 이때 nums[i] == val이라면
	2-1. 남은 배열의 길이를 구하기 위해 지워진 개수 removeCnt++
	2-2. temp[i] = 1로 초기화한다.
3. temp 배열을 i ~ nums.length - 1까지 반복한다.
	3-1. temp 배열을 누적합한다.
	3-2. 이때, temp[i] > 0 && nums[i] != val이면 nums[i - temp[i] = nums[i]

예를들어 nums = [0,1,2,2,3,0,4,2], val = 2일 때, 2번 과정을 거친 결과는 다음과 같다.

index		0 1 2 3 4 5 6 7
---------------------------
nums		0 1 2 2 3 0 4 2
temp		0 0 1 1 0 0 0 1
---------------------------
removeCnt	0 0 1 2 2 2 2 3

다음 3번 과정을 수행하면 temp 배열은 다음과 같이 채워진다.

index		0 1 2 3 4 5 6 7
---------------------------
nums		0 1 2 2 3 0 4 2
temp		0 0 1 2 2 2 2 3
---------------------------
removeCnt	0 0 1 2 2 2 2 3

마지막으로 4번 과정을 수행하면 지워지지 않은 원소들이 각각 앞으로 temp[i] 칸만큼 채워지게된다.

index		0 1 2 3 4 5 6 7
---------------------------
nums		0 1 3 0 4 0 4 2

결과적으로 nums.length - removeCnt를 리턴하고 nums의 0 ~ k-1 인덱스의 원소들은 지워지지 않은 값으로 채워지게 된다.

class Solution {
    public int removeElement(int[] nums, int val) {
        int totalLength = nums.length;
        int[] temp = new int[totalLength];

        int removeCnt = 0;
        for (int i = 0; i < totalLength; i++) {
            if (nums[i] == val) {
                removeCnt++;
                temp[i] = 1;
            }
        }

        for (int i = 1; i < totalLength; i++) {
            temp[i] += temp[i - 1];
            if (nums[i] != val && temp[i] > 0) {
                nums[i - temp[i]] = nums[i];
            }
        }

        return totalLength - removeCnt;
    }
}

개선하기

풀이한 방식은 $O(2n)$(n= nums.length)의 시간복잡도를 갖는다. 하지만 풀고나니 2번 과정과 3번 과정을 합칠 수 있을 것 같아 합쳐 $O(n)$의 시간복잡도로 해결하였다.

class Solution {
    public int removeElement(int[] nums, int val) {
        int totalLength = nums.length;
        int[] temp = new int[totalLength];

        int removeCnt = 0;
        for (int i = 0; i < totalLength; i++) {
            if (i > 0) {
                temp[i] += temp[i - 1];
            }

            if (nums[i] == val) {
                removeCnt++;
                temp[i] += 1;
            } else {
                nums[i - temp[i]] = nums[i];
            }
        }

        return totalLength - removeCnt;
    }
}

허무..

이런 결과를 받고보니 뿌듯했다. 하지만 다른 Solution을 보니 허무했다... 방식은 같지만 내가 너무 어렵게 풀었던 것 같다. 나는 누적합을 구하기 위해 temp라는 임시 배열을 생성했지만 사실 누적합된 값은 앞에서 val에 해당하는 값이 지워진 개수(removeCnt)와 같다. temp 배열은 필요가 없다(temp 배열의 크기만큼 메모리를 아낄 수 있다). 결국 nums[i] != val이 아닐 때 지워진 값의 개수 칸만큼 이동하면 된다. 즉 nums[i] != val이면 nums[i - removeCnt] = nums[i]와 같다.

class Solution {
    public int removeElement(int[] nums, int val) {
        int removeCnt = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == val) {
                removeCnt++;
            } else {
                nums[i - removeCnt] = nums[i];
            }
        }

        return nums.length - removeCnt;
    }
}