[LeetCode/Top Interview 150] [Array / String] 27. Remove Element

문제 링크: https://leetcode.com/problems/remove-element/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: easy

문제:

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Return k.
Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
// It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.

Constraints:

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

전략:

stream, filter로 nums 내부의 val과 일치하지 않는 값의 "수"만 반환한다.
내부 함수 구현문제라 nums 배열을 수정할 필요도 존재함.

코드 구현(실패):

class Solution {
    public int removeElement(int[] nums, int val) {
        nums = Arrays.stream(nums).filter(i -> i != val).toArray();
        return nums.length;
    }
}
// nums 배열에 변경사항이 적용되지 않는 문제가 발생하여 통과하지 못함.

코드 구현:

class Solution {
    public int removeElement(int[] nums, int val) {
        int[] tempnums = Arrays.stream(nums).filter(i -> i != val).toArray();
        int k = tempnums.length;
        System.arraycopy(tempnums, 0, nums, 0, k);
        return k;
    }
}
// 깊은 복사로 해결

실행결과:
Time: 4 ms (7.86%), Space: 41.2 MB (22.94%) - LeetHub
https://github.com/1-vL/LeetCode/tree/main/0027-remove-element

개선 방안:

stream 보다 for 문이 더 빠르고, nums 배열도 직접 다룰 수 있어 편하긴 할 것 같다.
Arrays.sort 로 정렬하고 for 문으로 순회하며 val 값 나오는 위치 인덱스 저장 후 val값이 아닌 값 부터는 해당 인덱스 기준으로 덮어씌워도 되지 않을까?

class Solution {
    public int removeElement(int[] nums, int val) {
        int val_index = -1;
        int k = 0;
        boolean start = false;
        Arrays.sort(nums);
        for (int i=0; i<nums.length; i++) {
            if (val == nums[i]) {
                if (!start) {
                    val_index = i;
                    start = true;                    
                }
            } else {
                k++;
            }
            if (start && val != nums[i]) {
                nums[val_index++] = nums[i];
            }
        }
        return k;
    }
}
08/23/2023 01:45	Accepted	1 ms	40.9 MB	java

Discuss 탭의 타인 코드:

class Solution {
    public int removeElement(int[] nums, int val) {
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[index] = nums[i];
                index++;
            }
        }
        return index;
    }
}
08/23/2023 01:39	Accepted	0 ms	40.7 MB	java

회고:
Stream 연습 겸 해서 처음 생각난 방식으로 Stream을 사용했었는데 결과적으로 Java의 Reference를 배운 셈이 되었다.
for문 방식으로 하는 경우 나머지 배열이 중요하지 않으므로 앞 부분만 신경써서 덮어씌우고, 덮어씌운 요소의 수=k인 것을 이용한 부분이 확실히 효율적인 것 같다.

참고: https://jjam89.tistory.com/230